斐波那契数列递归c#方法

Question

我很难写出一个使用递归 return 斐波那契数列的方法。

我的迭代方法如下：

public static string Fibonacci(int n)
{

    if (n < 2)
        return "1";
    int[] numbers = new int[n];
    numbers[0]=0;
    numbers[1]=1;
    for (int i = 2; i < n; i++)
    {
        numbers[i] = numbers[i - 1] + numbers[i - 2];

    }
    return string.Join(" ", numbers);
}

我希望将上述方法更改为递归调用但具有相同的签名即 return 类型是字符串并且它 returns 斐波那契数列例如 0,1,1,2,3,5 ,8,13,21,34,55

我用谷歌搜索，但在任何地方我都看到它是使用 Console.WriteLine() 完成的，即值被打印到屏幕上但不是 returned 作为函数中的字符串。

谢谢

Answer 1

当然，网上有很多斐波那契算法的例子，递归的和其他的。自然地，递归实现的关键是从递归调用中获取结果，将其与当前结果组合，然后 return that 给调用者。

所以让我们从基本的斐波那契思想开始，使用递归方法在生成数字时写出数字：

void Fibonacci(int iMinus2, int iMinus1, int count)
{
    if (count == 0) return;

    int current = iMinus2 + iMinus1;

    Console.WriteLine(current);

    Fibonacci(iMinus1, current, count - 1);
}

那么问题来了，我们如何调整上面的内容，使其 return 成为 string 而不是一次一个地写出数字。同样，请记住，关键是始终有办法将当前结果与先前调用的组合结果组合起来。在这种情况下，这意味着我们要将当前数字转换为字符串，并将该字符串添加到由递归调用 return 编辑的字符串（即所有数字 after 当前人数：

string Fibonacci(int iMinus2, int iMinus1, int count)
{
    if (count == 0) return null;

    int current = iMinus2 + iMinus1;
    string nextNumbers = Fibonacci(iMinus1, current, count - 1);

    return nextNumbers != null ?
        current.ToString() + ", " + nextNumbers : current.ToString();
}

注意：以上内容比我建议的要复杂一些，因为它处理了在没有更多下一个数字时避免添加逗号的问题。还有其他方法可以实现这一点，但我更喜欢实现递归方法，这样终止条件由被调用者而不是调用者处理。

我把它留作 reader 的练习来处理上面的调用，以及如何处理短序列（即只看第一个或前两个数字的退化情况在序列中）。 :)

注意：你的问题听起来很像作业题。如果是这样：这些在 Stack Overflow 上是合适的，但我怎么强调都不应该将 Stack Overflow 视为您老师的替代品。我们很乐意就家庭作业问题提供建议和帮助，但重要的是您要与老师保持联系并寻求他们的建议，以便他们更好地了解您遇到问题的地方。

斐波那契数列递归c#方法

Fibonacci Series recursive c# method

c#

recursion

fibonacci