递归和斐波那契数列 [英] Recursion and fibonacci sequence

问题描述

如何获取此代码以打印给定术语的斐波那契数列的所有值?现在，它仅显示最后一个字词

How do I get this code to print all values of the fibonacci sequence of given terms? Right now it prints only the last term

#include <stdio.h>

int fibonacci(int n){

    if (n==2)
        return 1; 
    else
      return fibonacci(n-1) + fibonacci(n-2);   

}


int main()
{

    int n;
    int answer;
    printf("Enter the number of terms you'd like in the sequence\n");
    scanf("%d",&n);

    answer = fibonacci(n);
    printf("The answer is %d\n", answer);

}

推荐答案

您的基本情况不正确.当 n == 2 时，您将调用 fibonacci(1)和 fibonacci(0).后者将继续向下，直到您耗尽堆栈空间为止.

Your base case is incorrect. When n==2, you'll call fibonacci(1) and fibonacci(0). The latter will continue downward until you run out of stack space.

您应该检查数字小于等于基本情况:

You should check for numbers less than to equal to the base case:

if (n<=2)

如果要打印所有值，则由于双重递归，因此无法以函数当前的结构方式进行打印.

If you want to print all the values, you can't do it the way the function is currently structured because of the double recursion.

如果您跟踪以前计算出的数字，则可以完成此操作.然后，只有在第一次计算数字时才打印出一个数字(并执行递归)，否则从列表中查找并继续.

If you keep track of the numbers you've calculated previously, it can be done. Then you only print out a number (and perform recursion) the first time you calculate a number, otherwise you look it up from the list and continue.

int fibonacci(int n){
    static int seq[50] = {0};

    if (n > 50) {
        printf("number too large\n");
        return 0;
    }
    if (seq[n-1] == 0) {
        if (n<=2) {
            seq[n-1] = 1;
        } else {
            seq[n-1] = fibonacci(n-1) + fibonacci(n-2);
        }
        printf("%d ", seq[n-1]);
    }
    return seq[n-1];
}

输出:

Enter the number of terms you'd like in the sequence
10
1 1 2 3 5 8 13 21 34 55 The answer is 55

请注意，上述函数的上限为50，因为结果对于该范围附近的32位int而言太大.

Note that the above function has a limit of 50, since the result is too large for a 32 bit int at around that range.

这篇关于递归和斐波那契数列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！