递归序列-泛型方法

Question

下面是Fibonacci数的经典递归示例

def fib(n):
    assert type(n) == int & n >= 0
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2) 

fib(5) #=> 8

当我们调用fib(5)时，当代码执行时，是否存在一个序列，在该序列中，fib() fcn的最后一行中的fib(n-1)和fib(n-2)将被执行-即。问一下，是先调用fib(n-1)部分，等待返回，然后再调用fib(n-2)部分，还是它们并行发生？

Answer 1

不，这两次计算都将按顺序进行，是的，这是计算斐波那契级数的一种非常浪费的方法。

一个浪费较少的递归函数返回两个连续的数字(当前和先前)：

def fib2(n):
  if n == 1:
    return (0, 1)
  else:
    prev_1, prev_2 = fib2(n-1)
    return (prev_1 + prev_2, prev_1)

def fib(n):
    value, _ = fib2(n)
    return value

一个更好的方法uses matrix exponentiation，效率更高。

Answer 2

首先计算fib(n-1)部分，然后计算fib(n-2)部分。