各種典型再帰関数を非再帰に変換する
再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。
再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。
典型的な再帰関数について、非再帰バージョンの書き方を以下にまとめる。
階乗
簡単にループで書ける。
末尾再帰なので末尾再帰 - Wikipediaのように簡単に変換できる。
再帰版
int factorial(int n) { if (n == 0) return 1; else return n * factorial(n-1); }
非再帰版
次のGCDに合わせてちょっと変な書き方。
int factorial2(int n) { int res = 1; while(1) { if (n == 0) return res; else { res *= n; n--; } } }
最大公約数（ユークリッドの互除法）
階乗と同じ感じ。
再帰版
int gcd(int a, int b) { if (b == 0) return a; else return gcd(b,a%b); }
非再帰版
int gcd2(int a, int b) { while(1) { if (b == 0) return a; int t = a; a = b; b = t%b; } }
アッカーマン関数
int ack(int m, int n) { if (m == 0) return n+1; if (n == 0) return ack(m-1,1); else return ack(m-1,ack(m,n-1)); }
できるだけループにしてみる。
int ack2(int m, int n) { while(1) { if (m == 0) return n+1; else if (n == 0) { m--; n = 1; } else { n = ack2(m,n-1); // ☆ m--; } } }
スタックを使って非再帰にする
int ack3(int m, int n) { stack<int> S; while(1) { if (m == 0) { n++; if (S.empty()) return n; else { m = S.top(); S.pop(); } } else if (n == 0) { m--; n = 1; } else { // ack2の☆部分を今から計算する // ☆部分の計算が終わったらスタックからm-1を取り出して先に進めるようにする S.push(m-1); n--; } } }
ハノイの塔
void hanoi(int n, char from, char work, char to) { if (n == 1) { printf("%c -> %c\n", from, to); } else { hanoi(n-1, from, to, work); printf("%c -> %c\n", from, to); hanoi(n-1, work, from, to); } }
できるだけループに
void hanoi2(int n, char from, char work, char to) { while(1) { if (n == 1) { printf("%c -> %c\n", from, to); return; } else { hanoi2(n-1, from, to, work); printf("%c -> %c\n", from, to); n--; swap(work,from); } } }
スタックを使って非再帰に。
スタックには元に戻るために必要な情報をすべて積んでおく。
struct P { int n; char from, work, to; }; void hanoi3(int n, char from, char work, char to) { stack<P> S; while(1) { if (n == 1) { printf("%c -> %c\n", from, to); if (S.empty()) { return; } else { P p = S.top(); S.pop(); n = p.n, from = p.from, to = p.to, work = p.work; printf("%c -> %c\n", from, to); n--; swap(work,from); } } else { S.push((P){n,from,work,to}); n--; swap(work,to); } } }
再帰下降構文解析
いきなりレベルアップ。
文法としては、括弧と+と-と*があるような数式を対象とする。
例えば、"2+3*(4+7)"
char s[1010]; // パースする文字列が入っている int term(int &i); int fact(int &i); int exp(int &i) { int p = term(i); while(s[i]=='+' || s[i]=='-') { char c = s[i++]; if (c == '+') { int a = term(i); p += a; } else p -= term(i); } return p; } int term(int &i) { int p = fact(i); while(s[i]=='*') { i++; p *= fact(i); } return p; } int fact(int &i) { if (s[i] == '(') { i++; int p = exp(i); assert(s[i++]==')'); return p; } else { int num = 0; while(isdigit(s[i])) { num *= 10; num += s[i]-'0'; i++; } return num; } }
とりあえず関数を１つにしてみる。
char s[1010]; // パースする文字列が入っている enum Type {EXPR, TERM, FACT}; int parse(Type t, int &i) { int p; if (t == EXPR) { p = parse(TERM, i); while(s[i]=='+' || s[i]=='-') { if (s[i++] == '+') p += term(i); else p -= term(i); } } else if (t == TERM) { p = fact(i); while(s[i]=='*') { i++; p *= fact(i); } } else if (t == FACT) { if (s[i]=='(') { i++; p = exp(i); assert(s[i++]==')'); } else { p = 0; while(isdigit(s[i])) { p *= 10; p += s[i]-'0'; i++; } } } return p; }
スタックを用いて非再帰にする。
スタックの中身としては、今処理するべきなのはどの関数（expr,term,fact）のどの部分かという情報がまず必要。
さらに、２項演算を実行するために左オペランドが何であったかという情報や、exprにおいて今処理しているのは+なのか-なのかという情報も必要。
ちなみにAOJで見かけたfura2さんのコードを大いに参考にしています。
enum Type {EXPR1, EXPR2, EXPR3, TERM1, TERM2, TERM3, FACT1, FACT2}; struct state { Type t; int v; bool f; // EXPR3用（+か-か） state(Type t) : t(t) {} state(Type t, int v) : t(t),v(v) {} state(Type t, int v, bool f) : t(t),v(v),f(f) {} }; int parse(const string &s) { int i = 0; int now = 0; // 直近に処理した”関数”の返り値 stack<state> S; S.push(EXPR1); while(!S.empty()) { Type t = S.top().t; int v = S.top().v; bool f = S.top().f; S.pop(); if (t == EXPR1) { // TERM1を処理 → EXPR2を処理というイメージ S.push(state(EXPR2)); S.push(state(TERM1)); } else if (t == EXPR2) { // nowにTERM1の結果が入っている if (s[i] == '+' || s[i] == '-') { S.push(state(EXPR3,now,s[i]=='+')); S.push(state(TERM1)); i++; } } else if (t == EXPR3) { // nowにTERM1の結果（右オペランド）が入っている // vに左オペランドが入っている if (f) now = v+now; else now = v-now; if (s[i] == '+' || s[i] == '-') { i++; S.push(state(EXPR3,now,s[i]=='+')); S.push(state(TERM1)); } } else if (t == TERM1) { S.push(state(TERM2)); S.push(state(FACT1)); } else if (t == TERM2) { if (s[i] == '*') { i++; S.push(state(TERM3,now)); S.push(state(FACT1)); } } else if (t == TERM3) { now = v * now; if (s[i] == '*') { i++; S.push(state(TERM3,now)); S.push(state(FACT1)); } } else if (t == FACT1) { if (s[i] == '(') { i++; S.push(state(FACT2)); S.push(state(EXPR1)); } else { // number now = 0; while(isdigit(s[i])) { now *= 10; now += s[i]-'0'; i++; } } } else if (t == FACT2) { // ()の後処理 assert(s[i++]==')'); } } return now; }
