斐波那契数列，为什么这个循环函数有效？

Question

我正在阅读一本编程书，其中一个示例是关于斐波那契数的，以及循环函数如何找到第 n 个斐波那契数。

代码如下所示：

Int fib (int n)
{
If (n<3)
Return (1);
Else
Return (fib(n-1))+(fib(n-2))
}

现在这并不准确，因为我是从手机上输入的，并且我了解代码是如何工作的，它会调用自身直到返回 1，然后将返回值相加，直到得到序列中位置的正确斐波那契数。

所以我不需要代码方面的帮助。我真正需要帮助的是理解为什么这是有效的。将所有回报相加如何得出正确答案？

请有人解释一下为什么这是有效的。谢谢。这让我抓狂。

Answer 1

递归是这样的：

1. 一个孩子睡不着，所以她
   妈妈给她讲了一个故事
   小青蛙
2. 睡不着，所以青蛙
   妈妈给她讲了一个故事
   小熊
3. 睡不着，所以小熊的
   妈妈给她讲了一个故事
   小黄鼠狼……
4. 睡着了。
5. ..小熊睡着了；
6. ……小青蛙睡着了；
7. ……然后孩子就睡着了。

来源

Answer 2

我建议了解递归是如何工作的。基本上 fib 函数使用较小的参数执行自身，直到参数降为 2，然后它只返回 1。

fib(1) = 1
fib(2) = 1
fib(3) = fib(2) + fib(1) = 1 + 1 = 2
fib(4) = fib(3) [ fib(2) + fib(1) = 1 + 1 = 2 ] + fib(2) = 2 + 1
...

了解其工作原理的一种方法是在调试器中逐步运行它。

Answer 3

斐波那契数被定义为前两个斐波那契数之和。这给出了以下结果：

1 1 2 3 5 8 13 ...

因此，对于第三个数字（1 1 2），您将获取找到前一个数字的结果 - 即第二个（1 1 2）数字并将其相加到上一个之前的数字 - 即第一个 (1 1 2) 数字。

你还必须明白，程序需要先计算前面两个数字的值，然后才能计算出你想知道的数字。因此，它不断调用自己 - 使用相同的方法 - 直到它计算完所有内容。

Answer 4

这是斐波那契数列的定义。

第 n 个斐波那契数返回第 (n-1) 个和第 (n-2) 个斐波那契数之和。

因此，我们可以通过归纳推理证明，如果 fib(n-1) 和 fib(n-2) 给出有效的第 (n-1) 个和第 (n-2) 个斐波那契数，则 fib(n) = fib (n-1)+fib(n-2) 将是有效的第 n 个斐波那契数。

基本步骤是 fib(1) 和 fib(2) 是正确的（即 fib(1)=fib(2)=1）...

Answer 5

理解递归的技巧是理解堆栈。

我位于一个名为 main 的函数中的第 2 行，所有局部变量都存储在我的堆栈帧中：

+------------------+
| main() variables | The stack frame
+------------------+

然后我调用 fib(3)，因此计算机推送我的当前位置（EIP）到堆栈，然后为 fib 创建一个新的堆栈帧并将其添加到堆栈中。我只能访问顶部堆栈帧：

+------------------+
| fib()  n = 5     | Top of stack (current frame)
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

在 fib 的第 4 行，它再次调用 fib，因此同样的情况再次发生：

+------------------+
| fib()    n = 4   | Top of stack
+------------------+
| EIP: fib @ 4,1   |
+------------------+
| fib()    n = 5   |
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

并且它一次又一次地执行此操作函数被递归调用。堆栈一直增长，直到有东西返回，此时，在 fib 的第 2 行，它返回 1。这会弹出顶部堆栈帧并丢弃它，然后将执行返回到保存的执行指针和程序从停止的地方继续

+------------------+
| fib()    n = 3   | Top of stack
+------------------+
    ... etc ...
+------------------+
| EIP: main @ 2,1  |
+------------------+
| main() variables | Bottom of stack
+------------------+

最终您最终会回到调用函数（或者当它变得太大时会出现堆栈溢出）。要记住的关键是，每次调用该函数时，它都会获得一个包含所有局部变量的新堆栈帧，并且保存您之前的位置。这就是递归。

主要问题是，在教人们递归时，每个人总是使用斐波那契数列，这意味着在一行上有两个递归函数调用。这是不必要的混乱，我相信你会同意的！

Answer 6

斐波那契数被定义为前两个斐波那契数之和。它们各自定义为前两个斐波那契数之和。等等，等等，直到达到1。明白吗？任何随机斐波那契数都可以定义为两个斐波那契数之和；这些可以递归地定义为两个斐波那契数之和等。也就是说，斐波那契数的定义基本上是递归的；也就是说，它的定义涉及它所定义的内容。

这些东西可能很棘手，但它对于理解递归和计算机科学非常基础。继续努力；它最终会点击。

Answer 7

这称为递归

Answer 8

本视频教程应该可以让您更好地了解斐波那契递归的工作原理

[链接] http://www.schooltrainer.com/study-material/computer-science/stepping-through-recursive-fibonacci-function.html

Answer 9

根据定义，斐波那契数列是该数列中前两个数字的总和（其中前两个数字是 0 和 1）。

因此，当您在一个位置获得斐波那契数列时，您可以将其重写为前两个斐波那契数列的总和。

使用递归，您可以执行此过程，直到“之前的两个斐波那契数”分别为 1 和 1（在此算法的情况下），然后继续将数字相加“备份”递归，直到返回到您的序列中的原始位置。