pythonのreturn文、再帰処理に関する質問(フィボナッチ数列)

Question

前提

フィボナッチ数列を用いてretutn文について学習しています。
下記のコードは、n番目の項の数字がprintされるもので、講師が書いたものです。

質問ですが、
なぜ4を入力すると3が出力されるのかが、わかりません。

nに4を入力した場合
fib(4 - 1) + fib(4 - 2)=fib(5)
そして、これを再帰処理し
fib(5 - 1) + fib(5 - 2)=fib(7)...
となるのが、私のreturn文に対する理解度での限界でした。
おそらく8行目の計算方法か、再帰処理の部分に間違いがあるのだと思います。

どのようなアルゴリズムで3という出力がなされるのかを教えていただきたいです。

とても初歩的な質問だとは思いますが、よろしくお願いします。

該当のソースコード

# n番目のフィボナッチ数を返す関数
def fib(n):
  # nが0または1の場合はそのまま返す
  if n == 0 or n == 1:
    return n
  # nが2以上の場合は再帰的に計算する
  else:
    return fib(n - 1) + fib(n - 2)

# 例: 10番目のフィボナッチ数を求める
print(fib(4)) #実行すると3が出力されます

Comments

[meg_]

> 講師が書いたものです。
その講師の方には質問しなかったのですか？

Answer 1

fib(4) の実行過程をツリー状に図示すると以下の様になります。

             fib(4)
          /          \
      fib(3)         fib(2)
     /      \       /      \
  fib(2)  fib(1)  fib(1)   fib(0)
  /     \
fib(1)  fib(0)

最終的な結果は以下の通りです。

fib(1) + fib(0) + fib(1) + fib(1) + fib(0) == 1 + 0 + 1 + 1 + 0 = 3

Answer 2

fib(4 - 1) + fib(4 - 2)=fib(5)

なぜ fib(3) + fib(2) のことを fib(5) と表しているのですか。その考えが間違っています。

Answer 3

そして、これを再帰処理し
fib(5 - 1) + fib(5 - 2)=fib(7)

いいえ、fib(4)に対して計算するのはfib(4-1)とfib(4-2)です