斐波纳契数,为什么这种反复出现的功能有效？

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）...