python - 再帰的なフィボナッチ関数はどのように導出されましたか?

Question

Python では、n 番目のフィボナッチ数を返すフィボナッチ数列の再帰関数は次のように記述できます。

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n-2) + fib(n-1)

この関数がどのように機能するかは理解できますが、もし誰かがこの関数を以前に見たことがない場合、どのように導出するのでしょうか?

ありがとう

Answer 1

これは、フィボナッチ数列の数学的定義の大まかな翻訳にすぎません。

フィボナッチ数列は次のように定義されます。

F ₀ = 0

F1 = ₁

F _n = F _n-1 + F _n-2

Python コードは基本的にこれを直接翻訳したものであることがわかります ( noff by 1 を除く)。