为什么斐波那契数列的索引需要小于或等于 1？

Question

对于作业，我需要创建一个代码来显示斐波那契数列中的元素 n。我已经知道怎么做了，你可以在下面找到我的代码，但我只是不明白为什么索引值需要低于或等于 1.

这是我的代码：

int ft_fibonacci(int index)
{
    if (index < 0)
        return (-1);
    if (index <= 1)
        return (index);
    else
        return (ft_fibonacci(index - 1) + ft_fibonacci(index - 2));
}

Answer 1

正如您应该已经知道的那样，当您编写递归函数时，您需要有一个您已经知道结果并且可以 return 它的基本情况，以停止应用递归。

斐波那契数列的数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, [...] 等等。现在，很明显第一个数字是 0。不过，您必须决定的是要分配给第一个数字的 index。

在您的函数中，此 if 代表您的基本情况：

if (index <= 1)
    return (index);

这将使 index = 0 的函数 return 0 和 index = 1 的 1 。因此，在您的情况下，您将 index = 0 分配给序列的第一个数字（即您从 0 开始计数）。

您需要 <= 1 因为递归调用是 fib(index -1) + fib(index - 2)，因此如果您没有两个基本情况，您的递归将永远不会停止。当您到达 index = 2 时，您的函数将调用 fib(1) + fib(0)，而这两个函数将分别调用 return 1 和 0，停止递归。

如果您想从 1 开始对斐波那契数进行编号，那么您应该使用：

if (index < 1) // invalid index, should not happen
    return -1;
if (index == 2)
    return 1;
if (index == 1)
    return 0;

或者更简洁：

if (index < 1) // invalid index, should not happen
    return -1;
if (index <= 2)
    return index - 1;

根据经验，请记住，只要您不需要处理负值（斐波那契数和您的指数不能为负），您应该使用 unsigned 类型（在本例中为 unsigned ft_fibonacci(unsigned index)).这也将消除对错误检查 if (n < 0) 的需要。您也不需要将 returned.

值括起来

unsigned ft_fibonacci(unsigned index)
{
    if (index <= 1)
        return index;
    else
        return ft_fibonacci(index - 1) + ft_fibonacci(index - 2);
}

为什么斐波那契数列的索引需要小于或等于 1？

Why does the index for the fibonacci sequence need to be less or equal to 1?

c

fibonacci