C言語 フィボナッチ数を求めるコード

問題

n番目のフィボナッチ数を返すコードを作成せよ。

• 引数が０より小さい場合は、-1を返す。

• 再帰的に実装する。

• 関数は以下の形を取ること

  • int fibo(int index);

• 禁止事項

  • ライブラリの使用は禁止
  • for、do...while、caseは禁止

自作コード

int fibo(int index)
{
    if(index < 0) return -1;
    if(index == 0) return 0;
    if(index == 1) return 1;
    if(index > 46) return 0;
    return fibo(index - 1) + fibo(index -2);
}

Aさんのコード

int fibo(int index)
{
    if (index < 0)
        return (-1);
    if (index == 0)
        return (0);
    if (index == 1)
        return (1);
    if (index > 46)
        return (0);
    return fibo(index - 1) + fibo(index - 2);
}

テストケース

# include <stdio.h>

int main()
{
    int i = 1;
    int x = 0;
    for(x = -3; x < 50; x++){
        i = fibo(x);
        printf("%dのフィボナッチ数：%d\n",x,i);
    }
    return (0);
}

所感

• 最初、int型の最大値を考慮したコードになっていなかった。intの最大値は常に意識する必要がある。

• メモ化再帰を使いたかったが、関数の形が決められているため使えなかった。

  • 試しにメモ化再帰で実装してみたら速さがあまりに違うので驚いた。

• テストケースで考慮したこと

  • マイナスの数の場合の挙動
  • 0,1のときの挙動
  • 46前後の挙動

おまけ　メモ化再帰を使用したフィボナッチ数を求めるコード

int fibo(int index, int a[])
{
    if(index < 0) return -1;
    if(index == 0) return 0;
    if(index == 1) return 1;
    if(index > 46) return 0;
    if(a[index] != 0) return a[index];
    return a[index] = fibo(index - 1, a) + fibo(index -2, a);
}

追記

2020/04/14
一ヶ月ぶりに似たような問題を解いたので戻ってきた。
書いてみたけど、うまく行かない。
メモ化再帰の部分で、staticをつけていなかった。
前回、ちゃんと理解できていなかった。
staticをつけることによって静的領域に値が保持され、計算結果が引き継がれる。
ここを理解できていなかった。復習大事。

// ここ重要！
static int A[46 + 1] = {0, 1};

# include <stdio.h>

int fibo(int n)
{
    static int A[46 + 1] = {0, 1};

    if (n < 0)
        return -1;
    if (n > 46)
        return 0;
    if (n >= 2 && A[n] == 0)
        A[n] = fibo(n - 1) + fibo(n - 2);
    return A[n];
}

int main(void)
{
    int N;

    scanf("%d", &N);

    printf("%d\n", fibo(N));
    return 0;
}