1. ホーム
  2. パフォーマンス

[解決済み】再帰と反復のどちらを選ぶ?

2022-04-01 17:45:47

質問

同じ目的を果たすことができるアルゴリズムにおいて、再帰の代わりにループを使用した場合、またはその逆を行った場合、パフォーマンスに影響があるのでしょうか?例:与えられた文字列が回文であるかどうかをチェックする。 多くのプログラマが、単純な反復アルゴリズムで対応できるにもかかわらず、再帰を見せびらかす手段として使っているのを見たことがあります。 コンパイラは、何を使うかを決めるのに重要な役割を果たすのでしょうか?

どのように解決するのか?

再帰的な関数が 末尾再帰的 (最終行が再帰呼び出し)。 テールリカーシオン コンパイラに認識され、反復処理に最適化されます(あなたのコードにある簡潔で明確な実装は維持されます)。

私なら、数ヶ月後、数年後にそのコードを保守しなければならない哀れな人(自分であれ、他の人であれ)にとって、最も理にかなっていて、最も分かりやすい方法でアルゴリズムを書きますね。 もしパフォーマンスの問題が発生したら、コードをプロファイリングして、それから反復処理に移行して最適化することを検討してください。 例えば メモ化 ダイナミックプログラミング .