这种递归是如何工作的?你能解释一下他们是如何获得输出的吗?

Question

function fnum = fib(n)
if (n == 1) || (n == 2)
fnum = 1;
else
fnum = fib(n-1) + fib(n-2);
end

您能否解释一下每个步骤如何针对给定输入输出。例如，输入 7 给我 13,5 给我 5，但我无法跟踪如何。我将非常感谢您的答复。

Answer 1

递归基本上意味着函数调用自身。

如果我们关注你的函数fib(3)，你会看到它的作用是调用fib(2)+fib(1)。这些值是定义的，并且是 1，因此它将返回 2。

如果你用fib(4)调用它，它将去计算fib(3)+fib(2)。您已经知道fib(3)的作用(请参阅上一段(，并且我们已经提到fib(2)返回1。

如果你用fib(5)调用它，它会去计算fib(4)+fib(3)。见上一段。

这是一种非常有用的编程方式，因为它是一个非常简单的函数来计算可以说更复杂的东西。最重要的是，你要确保任何递归函数都有很强的停止标准，否则它可以永远消失！

Answer 2

你知道斐波那契级数是如何定义的吗？此函数以递归方式实现这一点。

更长的答案

斐波那契级数定义为

n(1) = 1
n(2) = 1
n(k+1) = n(k) + n(k-1)

因此，当您将 5 作为参数时，扩展变为

n(4+1) = n(4)+n(3)
= n(3)+n(2)+n(2)+n(1)
= n(2)+n(1)+1+1+1
= 1+1+1+1+1
= 5

一个更简单的包络方法是从第一个索引开始，然后加上最后两个项以到达下一个索引。

1， 1， 2 <- (1+1(， 3 <- (2+1(， 5 <- (3+2(， ...

Answer 3

斐波那契级数被定义为f(1) = 1, f(2) = 1 and for all n > 2, f(n) = f(n-1) + f(n-2)

因此，当您调用fib(1)时，它会返回相同的1fib(2)。但是当你调用fib(3)时，它会返回fib(3-1) + fib(3-2)这是fib(2) + fib(1) = 2。然后当你调用fib(4)时，它会返回fib(3) + fib(2) = (fib(2) + fib(1)) + fib(1) = 3.递归地，斐波那契级数等于1, 1, 3, 5, 8, 13, 21, ...

对于 n 不同于 1 或 2 的代码，它会递归fib调用函数。当等于 1 或 2 时，它返回 1。