それ、非再帰で書けます - Qiita

まだ再帰関数書いてるの？ 再帰関数はプログラミング言語の有用な機能で、深さ優先探索をベースとする様々なアルゴリズムの実装として有用です。 その一方で、関数呼び出しはオーバーヘッドが大きく、定数倍が弱くなります。また、JavaやPythonなどのスタック領域の制限が厳し目の言語では深すぎる再帰のせいでRuntime Errorが発生する場合があります。 C++などのコンパイル言語ではインライン展開によって関数呼び出しのオーバーヘッド解消されることもありますが、再帰関数は中でもインライン展開の難易度が高く、深い再帰ではそのまま実行せざるを得ない状況になります。 ところが、再帰関数は生のスタックを自分で用意するなどして非再帰に書き直すことができます。（「停止する再帰的処理は常に同じ時間・空間計算量の非再帰処理に書き換えられる」、真っぽいのですが厳密な証明が見つけられなかったのでもしかしたら反例が

[manaten]

自分は意識低いので末尾再帰最適化できる言語で再起を書こうと思った

[xlc]

再帰を避けるためにスタックを自前で操作するというのは40年前のテクニックですな。確かCP/MのTurbo Pascal は再帰呼び出しができなかった。素直に再帰で書いた方がいいと思うぞ。

[Windymelt]

>この記事は再帰自体を全否定する趣旨ではありません。 >まだ再帰関数書いてるの？ 自分が書いてることに責任持ってほしい

[higgsino]

再帰が書ける人があえて非再帰で書くのと再帰が書けない人が非再帰で書くのは全然違う

[a235]

まあ再帰呼び出しはスタック＋ループに置き換えることができる、というのはアルゴリズムやコンパイラの教科書ならまず書いてある話ではある。／計算機科学ってちゃんと勉強すると物凄く捗るよ。

[indication]

組み込みだと再帰はスタック使用量が見積もれる物で、ある程度分岐予測が崩れても問題ない物しか許可されなかったから、実質禁止だったな…

[toaruR]

コンパイラ頑張れ＼(^o^)／インタプリタ頑張れ

[xsde]

再帰ではimmutableに書けるのに非再帰ではmutable変数が必要になっちゃうのは正直負けでは。競プロで定数倍高速化が必要な場面はいくつかあるけど再帰を非再帰に直したことはない。

[fukken]

再帰とループは意味的に等価（全ての再帰はループに書き換えられる。逆もまた然り）、とは何かで読んだ記憶があるが、証明まではわからないなぁ。

[programmablekinoko]

ぶっちゃけ再帰ってLispの人とかが表現の簡潔さ重視で使ってる印象がある。普通に手続き型のループで書いた方がコスト低い場合が多い（副作用バンバン使えるので）。

[diveintounlimit]

速度が必要な側面での局所最適化のためにやるウルトラCかなぁ

[puhu208n]

人にはあらゆるループを再帰で書きたくなる時期と、それを恥に思い始め全てをループに書き直す時期と、そして「「「エンジニアリング」」」って何なんだ……と虚脱する時期がある

[lli]

ループと再帰でこんなに違うんだなぁ

[shunkeen]

早すぎる最適化は諸悪の根源と言うが、競プロの文脈がない場所で定数倍高速を主張しすぎると、競プロの競技性は諸悪の根源とか言われそう／再帰でも非再帰でも相互に書き換えられる方が技術力が高いのは確かだけど

[onesplat]

ブコメ再帰好きすぎだろ。どのくらい本気で言ってるのかわからなくて怖いわ。再帰外しとか頻繁とまでは言わないが普通にやるからな？末尾再帰最適化なんてアテにするくらいならループにしろ

[Sediment]

後で読む。競技プログラミング以外で再帰は使ったことないライトユーザーです。

[tkni2005]

すき

[nakag0711]

binomial()はこれコンパイル通るの？多分n_はN、r_はRかな。大文字使うならconstにした方がいいけど／expr()は領域外アクセス発生してる。stringは単なるC文字列と違って文字列の最後の\0にイテレータでアクセスできない仕様

[mozukuyummy]

木構造の問題は非再帰で書くとデバッグの時にツリーがたどりやすい(スタックをとりあえず全部書き出してじっくり考えられる)と思ってるんだけど自分だけかな、、、？

[kazoo_oo]

“PyPyは再帰が苦手です” 知らんかった。

[door-s-dev]

こうゆう事を言い出すのは大分競プロのよくない面に染まってる気がする

[taruhachi]

「Q:再帰とは？、、、A:自己参照のこと。Q:自己参照とは？、、、A:再帰の事。」を思い出した。

[hase0510]

KowerKointさん、名前が好きすぎる。かわこ！

[kusigahama]

こういう戦争なら楽しいんだけどな

[flont]

早すぎる最適化は諸悪の根源なので理由がなければまず再帰で実装するが、競プロ限定なら常にループに変換するのもありか

[maninthemiddle]

再帰で書いた方が分かりやすいんだよな

[Iridium]

自動非再帰化モジュール　桃白白

[Cald]

"特にPyPyは"(中略)"苦手です。"

[ene0kcal]

息をするように再帰処理を書くガチ勢が来るんじゃないかと思ったら、やはり来訪されてました（尊敬）。ディープな知識が得られる話題なので期待。もしかしたらshiro氏がネタを調理してくれるかも|дﾟ)ﾁﾗｯ

[Shinwiki]

再帰のいみ

[deep_one]

私が再起処理で頭に浮かんだのは「入れ子になった構造の処理」みたいなものなのでまるで関係なかった。（何重の入れ子になっているデータが来るのかプログラミング時点では分からない。）

[kogule]

末尾呼出しを最適化すればいいだけの話をここまで長々と書かなきゃならないなんて，人類はいつになったら再帰呼出しを使いこなせるようになるんだろう。

[n314]

言語を指定しないのなら、末尾呼び出し最適化について触れないといけないんじゃないかな？