无法理解该算法的行为

Question

在学习 Michael Goodrich 的《算法》一书时，我发现了这种“不同于往常”的递归算法来计算第 n 个斐波那契数。 该算法在书中没有太多解释，我想出的唯一答案是 (1,1) .

def fibonacci(n):
    if n<=1:
        return (n,0)
    else:
        (a,b) = fibonacci(n-1)
        return (a+b,a)
print(fibonacci(5))

它确实工作得很好，但我只是不明白它是如何工作的，而且我确实知道递归是如何工作的。 如有任何帮助，我们将不胜感激。

Answer 1

在每个递归函数中，都有（必须）一个停止点，它是一个条件和一个return值（对于你的例子 if n<=1: return (n,0)）

所以在你的例子中你有：

F(5) => F(4) => F(3) => F(2) => F(1);

F(1) returns (1,0)

• 所以 F(2) 通过第 5 行到达第 6 行。并且 F(2) return (1,1).
• 现在 F(3) 通过第 5 行到达第 6 行。并且 F(3) return (2,1).
• 现在F(4)通过第5行到达第6行。而F(4)return(3,2).
• 现在 F(5) 通过第 5 行到达第 6 行。并且 F(5) return (5,3).

结果将是 (5,3)。