この記事は再帰自体を全否定する趣旨ではありません。 両方の良さを理解した上で非再帰で書きたいと思ったときの参考にしていただければと思います。 まだ再帰関数書いてるの? 再帰関数はプログラミング言語の有用な機能で、深さ優先探索をベースとする様々なアルゴリズムの実装として有用です。 その一方で、関数呼び出しはオーバーヘッドが大きく、定数倍が弱くなります。また、JavaやPythonなどのスタック領域の制限が厳し目の言語では深すぎる再帰のせいでRuntime Errorが発生する場合があります。 C++などのコンパイル言語ではインライン展開によって関数呼び出しのオーバーヘッド解消されることもありますが、再帰関数は中でもインライン展開の難易度が高く、深い再帰ではそのまま実行せざるを得ない状況になります。 ところが、再帰関数は生のスタックを自分で用意するなどして非再帰に書き直すことができます。(「停
![それ、非再帰で書けます - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/731d820939994bc455b2997e0671b0e04654f3f5/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-9f5428127621718a910c8b63951390ad.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTkxNiZoPTMzNiZ0eHQ9JUUzJTgxJTlEJUUzJTgyJThDJUUzJTgwJTgxJUU5JTlEJTlFJUU1JTg2JThEJUU1JUI4JUIwJUUzJTgxJUE3JUU2JTlCJUI4JUUzJTgxJTkxJUUzJTgxJUJFJUUzJTgxJTk5JnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWNsaXA9ZWxsaXBzaXMmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz0zNmU1ZDRiNTY1YWJmMTQ2YjMwYmQ4ZTBiOWQwNGU4Zg%26mark-x%3D142%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTcxNiZ0eHQ9JTQwS293ZXJLb2ludCZ0eHQtY29sb3I9JTIzMjEyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTMyJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnM9ODE4M2YzNjk0ZDhmNWJjODgzM2QxMDI3YzAwMDA1ZWQ%26blend-x%3D142%26blend-y%3D491%26blend-mode%3Dnormal%26s%3D8e9f7fbb6a2911ae984fd94de330167a)