C言語について質問です。フィボナッチ数列を求める再帰関数作成したいです。

C言語について質問です。
フィボナッチ数列を求める再帰関数作成したいです。
ただし、なるべく少ない呼び出し回数にしたいです。
僕は普通に
int fib(int n){
If(n == 0)
return 0;
else If(n == 1)
return 1;
else
return fib(n-1)+fib(n-2);
}
みたいに組んだんですけど、先生曰くもっと少なくできるそうです。考え方だけでもいいので、教えてください!

#1

(1150928647さん)
再帰呼び出しの時、メモ化すればいいです。

#include \u003cstdio.h>

int data[100] = {0};
int cnt;

int fibo2(int n) {
    cnt++;
    if (n \u003c= 1) {
        return n;
    }
    if (data[n]) {
        return data[n];
    } else {
        data[n] = fibo2(n - 1) + fibo2(n - 2);
        return data[n];
    }
}

int fibo1(int n) {
    cnt++;
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo1(n - 1) + fibo1(n - 2);
    }
}

int main() {
    int n = 10;
    cnt = 0;
    printf(\"fibo1(%d) = %d\
\", n, fibo1(n));
    printf(\"再帰呼び出し回数:%d回\
\", cnt);
    printf(\"\
\");
    cnt = 0;
    printf(\"fibo2(%d) = %d\
\", n, fibo2(n));
    printf(\"再帰呼び出し回数:%d回\
\", cnt);

    return 0;
}
ー 実行結果 ー
fibo1(10) = 55
再帰呼び出し回数:177回

fibo2(10) = 55
再帰呼び出し回数:19回