recursion - 二分探索木を実装するために反復的または再帰的ですか？

Question

私は今、データ構造とアルゴリズムを学んでいます。

私の講義ノートには、再帰的メソッドを使用して実装される二分探索木の実装があります。これは洗練された方法ですが、私の質問は実際のコードにあります。バイナリ検索ツリーを再帰的に実装すると、ツリーの高さ/深さの数値が大きい場合、大量の呼び出しスタックが生成されますか。

再帰は多くのデータ構造の概念を理解するための重要な概念であることを理解していますが、実際のコードで再帰を使用することを選択しますか？

Answer 1

木は本質的に再帰的です。ツリーの各ノードはサブツリーを表し、各ノートの各子はそのサブツリーのサブツリーを表すため、特に他の人がコードを編集および保守する必要がある場合は、再帰が最善の策です。

さて、IFの深さがコールスタックの問題になるのは、データ構造にさらに深刻な問題があるのではないかと心配しているからです（データ構造が非常に大きいか、非常に不均衡です）。

Answer 2

「再帰は多くのデータ構造を理解するための重要な概念であることを理解していますが、実際のコードで再帰を使用することを選択しますか？」

最初に再帰について学んだ後、私は同じように感じました。しかし、ソフトウェア業界で1年以上働いてきた私は、再帰の概念を使用していくつかの問題を解決してきたと言えます。多くの場合、再帰はよりクリーンで、理解/読み取りが容易で、まったく優れています。そして、前の答えのポイントを強調するために、ツリーは再帰的なデータ構造です。IMO、BSTをトラバースする他の方法はありません:)

Answer 3

多くの場合、コンパイラーはコードを最適化して、再帰呼び出しごとに新しいスタックフレームを作成しないようにすることができます（たとえば、末尾再帰を検索します）。もちろん、それはすべてアルゴリズムとデータ構造に依存します。ツリーが適度にバランスが取れていれば、再帰的アルゴリズムが問題を引き起こすことはないと思います。

Answer 4

再帰は直感的でエレガントであり、明確で簡潔なコードを生成するのは事実です。また、クイックソート、DFSなどの一部のメソッドを繰り返し実装するのは非常に難しいことも正しいです。しかし実際には、すべての関数呼び出しのために、再帰的な実装は反復的な実装と比較するとほとんどの場合遅くなります（パフォーマンスの低下を実際に理解するには、単一の関数呼び出しに対して簿記アセンブラーが行う必要がある量を学ぶことをお勧めします）。

私たちが話している最適化は、一般的にすべての再帰的方法に適用できるわけではなく、多くのコンパイラーとインタープリターはそれらをサポートしていません。

したがって、要約すると、データの構造など、パフォーマンスが重要なものを記述している場合は、再帰を避けてください（または、コンパイラー/インタープリターがカバーしていることが確実な場合は、それを使用してください）

PS：CLRS（アルゴリズムの概要、290ページ、最後の行）は、BSTの反復検索手順が再帰的な検索手順に比べて高速であることを示しています。