各種典型再帰関数を非再帰に変換する - 競技プログラミング+αなブログ
再帰関数はあんまり再帰が深くなるとスタックオーバーフローの危険があり、できれば非再帰で処理を書きたいというケースが稀にある。 再帰関数はスタックを使えば非再帰で書けるとたまに聞くが、実際どうやれば良いか分からなかったので調べてみた。 典型的な再帰関数について、非再帰バージョンの書き方を以下にまとめる。 階乗 簡単にループで書ける。 末尾再帰なので末尾再帰 - 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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
recursion-to-iteration series - Tom Moertel’s Blog
