时间戳

首页 > 解决方案 > 为什么斐波那契数列的索引需要小于或等于 1？

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

问题描述

对于分配，我需要创建一个可以显示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));
}

标签： cfibonacci

解决方案

您应该已经知道，当您编写递归函数时，您需要有一个基本案例，您已经知道结果并可以返回它，以停止应用递归。

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

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

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

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

您需要<= 1，因为递归调用是fib(index -1) + fib(index - 2)，因此如果您没有两个基本情况，您的递归将永远不会停止。当您到达 时index = 2，您的函数将调用fib(1) + fib(0)，这两个函数将分别返回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)。您也不需要在返回的值周围加上括号。

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

推荐阅读