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);

}

回答1:

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)

EDIT:

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];
}

Output:

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

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.