斐波那契递归如何在 C# 中工作

Question

我正在努力理解下面的斐波那契代码：

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 的函数。虽然答案是正确的，因为斐波那契数列的第 7 个元素是 13:

1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th
1    1   2   3   5  8   13  21  34   55

现在我正在尝试在我自己的论文中复制关于斐波那契递归如何工作以及 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?

我试图在线查看，但没有解释这个正确的斐波那契数列递归函数是如何工作的。代码是正确的，输出也是正确的，但我无法使用上面的纸上序列复制它。就像7的输入对我来说是15。

Answer 1

你只需要仔细扩展你的序列，仅此而已，这里没有魔法。

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
     = 13

Answer 2

{[F(4) + F(3)] + [F(3) + F(2)]} + {[F(3) + F(2)] + [F(2) + F(1)]}
=   3  +   2   +    2  +   1    +     2  +   1   +    1  +   1 = 13

Answer 3

我正在阅读你的问题是上述算法背后的逻辑是什么。我坚信的一件事是 "One size does not fit all"，这是一个很好的例子。

计算第 n 个斐波那契数的快速解决方案是递归地添加数字，直到第 n 个循环完成。相反，上述算法试图以相反的顺序推导出第 n 个斐波那契数。

这里的目标是找到第 n 个斐波那契数，根据定义，它必须是前两个数的总和，而前两个数又是前两个数的总和。

按照这个定义，您可以从我创建的图表中看到 x 必须是 y = x - 1 和 z = x - 2 的总和等等。

Answer 4

这是我喜欢向初学者解释递归的一种方式。

让我们想象一个稍微简单的 "pseudo code" 语言版本的程序：

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.

您可以将像这样的简单函数中的一般函数激活简单地想成 "what if I had the function body with all its formal parameters replaced with their argument values?" 如果您这样想，那么递归就变得更直接了。

当然这并不是运行时真正实现的方式，而且这忽略了控制流、变量突变等很多方面。但作为一种在你的职业生涯早期理解递归的方法，我认为这是一个很好的方法。

斐波那契递归如何在 C# 中工作

How Does Fibonacci Recursion Works in C#

c#

recursion

fibonacci