Fibonacci递归在C#中是如何工作的
我正在努力理解以下Fibonacci代码：
private static int mtdFibonacci(int number)
{
if (number == 0) return 0;
if (number == 1) return 1;
return fncRecursive(number - 1) + fncRecursive(number - 2);
}基本上，我很难把它作为一个函数来创建，一个7的输入等于13。尽管答案是正确的，因为Fibonacci序列的第7个元素是13：
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th
1 1 2 3 5 8 13 21 34 55现在，我正在尝试复制我自己的论文中关于Fibonacci递归工作以及c#如何解决它的代码：
if n is 7:
return F(7) = F(7-1) + F(7-2)
return F(7) = F(6) + F(5)
return F(7) = [F(5) + F(4)] + [F(4) + F(3)]
return F(7) = {[F(4) + F(3)] + [F(3) + F(2)]} + {[F(3) + F(2)] + [F(2) + F(1)]}
return 15?我试着在线检查，但是对于Fibonacci序列的这个正确的递归函数是如何工作的，没有任何解释。代码是正确的，输出是正确的，但我不能在上面的纸张序列上复制它。就像7的输入对我来说是15。
回答 4
Stack Overflow用户
发布于 2017-05-14 13:50:00
你只需要小心地扩展你的序列，仅此而已，这里没有魔法。
F(7) = F(6) + F(5)
= F(5) + F(4) + F(4) + F(3)
= F(4) + F(3) + F(3) + F(2) + F(3) + F(2) + F(2) + F(1)
= F(3) + F(2) + F(2) + F(1) + F(2) + F(1) + F(2) + F(2) + F(1) + F(2) + F(2) + F(1)
= 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
= 13Stack Overflow用户
发布于 2017-05-14 14:47:40
以下是我喜欢向初学者解释递归的一种方法。
让我们想象一下您的程序的一个稍微简单的“伪代码”语言版本：
f(n) => if n < 3 then 1 else f(n-1) + f(n-2)这不是合法的C#，但请仔细阅读并确保您理解这里的部分。
现在，我们要玩一个小游戏，只用文字。游戏规则如下：
- 如果我们看到
f(some number)，那么我们就用( the if expression with all the n's changed to some number )替换它。
我们现在需要更多的规则，但让我们从这个开始。假设我们有：
f(5)我们遵守规则。我们用
(if 5 < 3 then 1 else f(5-1) + f(5-2))接下来的规则：
number < number被true或false取代- 将
number - number替换为它们的差异 - 将
number + number替换为它们的和。 - 将
(number)替换为number，条件是(.f之前没有f
好的，应用这些规则：
(if false then 1 else f(4) + f(3))最后规则：
if false then X else Y被Y.if true then X else Y替换为X.
应用它：
(f(4) + f(3))现在再次应用第一条规则：
((if 4 < 3 then 1 else f(4-1) + f(4-2)) + (if 3 < 3 then 1 else f(3-1) + f(3-2))继续适用规则：
((if false then 1 else f(3) + f(2)) + (if false then 1 else f(2) + f(1))
(f(3) + f(2)) + (f(2) + f(1))让我们跳过几步。你看到f(3)将被(f(2) + f(1))取代，f(2)和f(1)将被(1)取代，对吗？
(((f(2) + f(1)) + (1)) + ((1) + (1))
(((f(2) + f(1)) + 1) + (1 + 1)
(((f(2) + f(1)) + 1) + (2)
(((f(2) + f(1)) + 1) + 2再跳几步。如果他们不清楚，那就亲自动手
((((1) + (1)) + 1) + 2
(((1 + 1) + 1) + 2
(((2) + 1 ) + 2
((2 + 1)) + 2
((3)) + 2
(3) + 2
3 + 2
5我们就完蛋了。仅用几个简单的字符串替换规则，我们就可以得出f( 5 )等于5。
在简单的函数中，您可以认为函数激活通常是这样的：“如果函数体的所有形式参数都被它们的参数替换了呢？”如果你这样想的话，递归就变得更简单了。
当然，这并不是运行时真正实现的方式，这忽略了控制流、变量突变等许多方面。但是作为一种在你职业生涯早期理解递归的方法，我认为这是一个非常好的方法。
Stack Overflow用户
发布于 2017-05-14 14:00:08
{[F(4) + F(3)] + [F(3) + F(2)]} + {[F(3) + F(2)] + [F(2) + F(1)]}
= 3 + 2 + 2 + 1 + 2 + 1 + 1 + 1 = 13https://stackoverflow.com/questions/43964574
复制相似问题
腾讯云开发者
