Search on the blog

2014年2月28日金曜日

再帰呼び出しをスタックを使って書き換える

蟻本に以下のようなことが書かれています。

 関数の呼び出しはスタックで実現されています。したがって、再帰関数は再帰呼び出しの代わりにスタックを用いて書き直すこともできます。

実際に再帰呼び出しをスタックで書き直すとどんな感じになるか書いてみました。以下はn番目のフィボナッチ数を計算する処理です。
こうやって書いてみると、
  • DFS = スタック
  • BFS = キュー
という対比が分かって勉強になりました。

あまり綺麗に書けている気がしないので、こうやるともっと綺麗に書けるなどあれば教えてください。
#include <iostream>
#include <stack>

using namespace std;

struct frame {
    int x;
    int index;
    long long ret;

    frame(int x) : x(x), index(0) {
        ret = x <= 1 ? x : 0;
    }
};

long long fibonacci(int n) {
    stack<frame> stk;
    stk.push(frame(n));

    long long ret = -1;
    while (!stk.empty()) {
        frame &f = stk.top();
        
        if (f.x <= 1 || f.index == 2) {
            ret = f.ret;
            stk.pop();
            if (stk.empty())
                break;
            stk.top().ret += ret;
        } else {
            ++f.index;
            stk.push(frame(f.x - f.index));
        }
    }

    return ret;
}

int main(int argc, char **argv) {
    int n;
    cin >> n;

    cout << fibonacci(n) << endl;
 
    return 0;
}

0 件のコメント:

コメントを投稿