如何推导出递归的斐波那契函数？

Question

在python中,返回第n个斐波纳契数的Fibonacci序列的递归函数可写为:

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

我理解这个函数是如何工作的,但如果有人以前从未见过这个函数,那么如何得到它呢？

谢谢

Answer 1

它只是Fibonacci序列的数学定义的粗略翻译.

Fibonacci序列定义为:

F ₀ = 0

F ₁ = 1

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

您可以看到Python代码基本上是对此的直接翻译(除非使用n1 除外).