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

F ₁ = 1

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

可以看到，Python 代码基本上是直接翻译这个的（noff by 1 除外）。