Python3 再帰

Question

再帰 基礎

Def fib(x):
If x == 0 or x == 1:
Return 1
Else:
Return fib(x-1) + fib(x-2)
Print(fib(4))

この結果がなぜ5になるのか教えてください。よろしくお願いいたします。

Comments

[quickquip]

コードは実行できるように、せめて読めるように書いてほしいです。 https://teratail.com/help/question-tips#questionTips3-5 Pythonとして正しいコードではないです。

[ozwk]

「自分はこういう解釈をしていて、それに基づくとこのコードはこういう動作をするはずだから、こういう結果になるはずだが、実際は5になる。なぜか」というような書き方をしてください。

Answer 1

こんにちは。

再帰のコツは「呼び出した関数が返すであろう結果を信頼する」ことです。
関数定義を読めば分かる通り、fib(4)の結果は、「fib(3)とfib(2)を足したもの」であり、それ以外の何物でもないのです。
それがわかったら、次のステップとしてfib(3)とfib(2)がそれぞれどんな結果になっているのかを考えてみましょう。
そうして関数の定義を掘り進んだ後に残る結果を得るものが、再帰的定義です。

Answer 2

四つ目の結果は3です。
もし x == 0 or x == 1の場合は、4 3 2 1 0 五つ目の結果が得られました。

def fib(x):
    if x == 1 or x == 2:
        return 1
    else:
        return fib(x - 1) + fib(x - 2)
print(fib(4))