再帰処理と反復処理

再帰と反復と、両方とも繰り返し処理を扱うものだが、その使い分けとかをどうするか考えてみた。
とりあえず、それぞれの特徴をまとめると、

[再帰処理]

• 関数呼び出しを繰り返す
• 基底ケースに達したときに処理が終了する

[反復処理]

• 反復構造を明示的に利用して繰り返す（構造化プログラミング的）
• カウンタの値を見て終了する

Lispなどの言語では、反復処理は関数呼び出しによって行うというのは当たり前。
どちらかというとこの方が個人的にはわかりやすい。しかし、CやJavaでこれを行うと、
関数を延々と呼び続けるためスタック領域を無限に食い潰していくことになる。
当然メモリ使用量も増えるから効率が悪い。言語仕様のレベルというか、言語ができた背景というか、
うまく表現できないけれどかなり原始的な部分で再帰処理は反復と比較すると不利。
有名なフィボナッチ数列を再帰処理でやるプログラムを書くとすぐに応答が帰ってこなくなる。
４０回を超える再帰呼び出しをした時点で明らかに速度が遅くなった。
言語構造的に、関数を呼び出すときの処理とか、それを切り替える際のオーバーヘッドなどから
やっぱりCやJavaでは再帰呼び出しは極力避けるべきなんだと思った。
とりあえず、試したフィボナッチ数列の再帰処理コード。

main() {
    long x, sum;
    scanf("%ld", &x);
    fibonacci(x);
    return 0;
}

fibonacci(long x){
    if( x == 0 || x == 1 )return x;
    else return fibonacci(x - 1) + fibonacci(x - 2);
}

こっちが反復形式ソースコード

main() {
    long number;
    printf("Type int value: ");
    scanf("%ld", &number);
    double result = fibonacci(number);
    printf("Fibonacci(%ld) = %f\n", number, result);
    return 0;
}

double fibonacci(long n){
    long x = 0;
    double value1 = 0.0, value2 = 0.0;
    for( x ; x < n ; x++ ){
        if( x == 0 ){
            continue;
        }
        if( x == 1 ){
            value2 = (double)x;
            continue;
        }
        double new = value1 + value2;
        value1 = value2;
        value2 = new;
    }
    return value1 + value2;
}

反復の方が明らかに処理が早い。
再帰の場合は入力が40を超えたころから急に遅くなる。
そして、50になると処理が終わるまで６分を超えた。
反復の方は入力に70を入れてもほぼ瞬時に処理が終わる。
明らかに反復の方がソースコードが長いが、ソースコードが長い != 処理が遅いということを
証明するいい実験ができたと思う。なんかこう・・・しみじみとしてしまう。