再帰でハマる - C#

ループの代わりに再帰を使って繰り返し処理を行ってみたのだが、何やら予想外の動作になった。
「なぜそうなるのか？」についてまではまだたどり着いていないのであしからず。


N番目のフィボナッチ数を求める関数で説明すると、 まずwhile文で単純に処理すると以下のようになる。

static int Fibonacci_1(int num)
{
    int x = 0,
        y = 1,
        old_x;

    while (num > 0)
    {
        old_x = x;
        x = y;
        y = old_x + y;
        num--;
    }

    return x;
}

Usage

int n = 12;
Console.WriteLine(
    "{0}th:{1}", n, Fibonacci_1(n));
//12th:144

今度は再帰を行い同様の処理をしてみる。

delegate int[] Fib(int[] n, Fib fib);
static int Fibonacci_2(int num)
{
    Fib fib = (xy, fn) =>
    {
        if (num > 0)
        {
            num--;
            fn(new[] { xy[1], xy[0] + xy[1] }, fn);
        }

        Console.WriteLine("{0}, {1}", xy[0], xy[1]);//①

        return xy;
    };

    return fib(new[] { 0, 1 }, fib)[0];
}

上記と同様に使用してみると結果は以下のようになった。

144, 233
89, 144
55, 89
34, 55
21, 34
13, 21
8, 13
5, 8
3, 5
2, 3
1, 2
1, 1
0, 1
12th:0

何番目を求めても答えは0。
コード内の①の部分で出力されている回数とその内容が逆転しているのがへんだ。
私の頭の中ではこれが出力されるのは最後の一度だけなのだが、どうにも理解し難い結果が出てくる。
もし仮に毎回出力されたとしても、なぜにその内容が逆転しているのか？
出力されるなら「0,1」から始まり「144,233」で終わるはず。

誰か分かる方がいらっしゃたら教えて下さいマセマセ m(__)m

一応手探りで解決したモノが以下。

static int[] Fibonacci_5(int num)
{
    if (num == 0){return new[] { 0, 1 };}

    return ((Func<int[], int[]>)((n) =>
    {
        return new[] { n[1], n[0] + n[1] };
    }))(Fibonacci_5(--num));
}

これで思った通りの結果が得られるわけだが...
しかし、なぜこれで良いのか書いた本人は分かっていない...　(^_^;)
勝手にぐるぐるループしてるけど、そのとき"n"の値も勝手に書き変わっているので、出力するのは1回にすれば正しい結果になるはず、という発想で書いてみただけ。

処理に掛る時間はおよそ倍になるのでボツですなぁ。(-ω-;)

行き当たりばったりで良しとする思考回路じゃないのねん!!




追記:
思った通りの動作となるように書き直したものです。

delegate int Fib(int n1, int n2, Fib fib);
static int Fibonacci_3(int num)
{
    Fib fib = (n1, n2, fn) =>
    {
        if (num > 0)
        {
            num--;
            return fn(n2, n1 + n2, fn);
        }
        else
        {
            return n1;
        }
    };

    return fib( 0, 1 , fib);
}

はい、私だけスッキリ(^-^)

欲を言えば、Javascriptで言うところのarguments.calleeのようなことができたら、もっとシンプルに書けるんだけどなぁ。



MSDNにもフィボナッチ数を求めるコードが載っていた。

必要な部分だけを抜き出し、メソッドにすると以下になる。

static int Fibonacci_7(int n)
{
    if (n <= 1) { return n; }
    return Fibonacci_7(n - 1) + Fibonacci_7(n - 2);
}

一見シンプルで良さげだが、実際に使ってみると超遅い。
まあ、参考までに。