python - 如何创建递归函数来计算斐波那契数列

Question

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

如何使这个递归？当我运行程序并输入一个数字时，返回相同的数字

Answer 1

您的函数已经是递归的。您只需传入 0、1 或 5 以外的数字即可查看效果:

>>> def fib(n):
...     if n == 0:
...         return 0
...     elif n ==1:
...         return 1
...     else:
...         return fib (n-1) + fib (n-2)
... 
>>> fib(0)  # returns immediately, because n == 0
0
>>> fib(1)  # returns immediately, because n == 1
1
>>> fib(2)  # returns fib(1) + fib(0) == 1 + 0 == 1
1
>>> fib(3)  # returns fib(2) + fib(1) == (fib(1) + fib(0)) + 1 == (1 + 0) + 1 == 2
2
>>> fib(100) # returns fib(99) + fib(98) == (fib(98) + fib(97)) + (fib(97) + fib(96)) == ...
# This one takes a while because 2**100 calculations need to be completed
354224848179261915075