仅使用1个递归调用C的斐波那契数列

Question

[尝试使用递归函数来计算斐波那契数，但是我的代码正在使用2个递归调用。是否可以只使用一个？将n-1的fib数保存到数组或类似物中，然后在函数末尾添加数字，行得通吗？

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int fib(int n) {
    assert(n >= 0);
    if (n > 1) 
        return fib(n - 1) + fib(n - 2);
    else if (n == 1)
        return 1;
    else 
        return 0;
}

int main(void) {
    int n, f;
    printf("the nth number: ");
    scanf("%d", &n);
    f = fib(n);
    printf("%d \n", f);
    return 0;
}

Answer 1

也许像这样，以第n个和第（n-1）个斐波那契数为可变参数？

void fib(int n, int *fib_n, int *fib_n_1) {
    if (n == 0) {
        *fib_n = 0;
        *fib_n_1 = 1;
    }
    else if (n > 0) {
        fib(n - 1, fib_n, fib_n_1);
        int new_fib_n_1 = *fib_n;
        *fib_n += *fib_n_1;
        *fib_n_1 = new_fib_n_1;
    }
}

与...通话

int n, fib_n, fib_n_1;
//.... read n
fib(n, &fib_n, &fib_n_1);

Answer 2

函数“ fib”必须返回2个值。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void fib(int n, int * ra, int * rb) {
    assert(n>=0);
    if (n>1) {
        int ya,yb;
        fib (n-1, &ya, &yb);
        *rb = ya;
        *ra = ya + yb;
    } else if (n==1) {
        *ra = 1;
        *rb = 0;
    } else {
        *ra = 0;
        *rb = 0;
    }
}
int main(int argc, const char * argv[]) {
    int n;
    printf("the nth number: ");
    scanf("%d",&n);
    int ya,yb;
    fib(n, &ya, &yb);
    printf("%d \n", ya);
    return 0;
}

Answer 3

以下似乎有效：

int fib_in(int n, int cur, int prev) {
    if (n == 1 || n == 2) {
        return cur;
    }
    return fib_in(n - 1, cur + prev, cur);
}
int fib(int n) {
    fib_in(n, 1, 1);
}