10

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

代码如下所示：

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

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

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

请有人可以解释为什么这是有效的。谢谢。它快把我逼疯了。

4

9 回答 9

13

递归是这样的：

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

资源

于 2010-11-04T00:00:36.297 回答
9

我建议了解递归是如何工作的。基本上 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
...

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

于 2010-11-03T23:57:38.540 回答
5

这是斐波那契数的定义。

第 n 个斐波纳契数返回第 (n-1) 个和第 (n-2) 个斐波纳契数的总和。

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

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

于 2010-11-04T00:02:02.193 回答
5

斐波那契数被定义为前面两个斐波那契数的总和。这给出了以下内容：

1 1 2 3 5 8 13 ...

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

您还必须了解，程序需要先计算前面两个数字的值，然后才能计算出您想知道的数字。因此，它不断地调用自己——使用相同的方法——直到它计算出所有的东西。

于 2010-11-03T23:59:02.717 回答
3

理解递归的诀窍是理解堆栈。

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

+------------------+
| 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
+------------------+

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

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

当函数被递归调用时，它会一次又一次地这样做。堆栈不断增长，直到有东西返回，此时，在第 2 行fib，它返回 1。这会弹出顶部堆栈帧并将其丢弃，然后将执行返回到保存的执行指针，程序从中断处继续

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

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

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

于 2010-11-04T00:26:04.567 回答
2

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

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

于 2010-11-03T23:57:14.730 回答
1

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

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

于 2011-11-14T20:07:37.417 回答
1

这叫做递归

于 2010-11-03T23:57:26.573 回答
0

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

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

使用递归，你会经历这个过程，直到“以前的两个斐波那契数”是 1 和 1（在这个算法的情况下），然后继续将这些数字加在一起“备份”递归，直到你回到你的序列中的原始位置。

于 2010-11-04T00:01:39.210 回答