再帰アルゴリズムの深い理解、誤解された再帰

[[333118]]

再帰は、プログラミングの本で説明するのが最も難しい部分である魔法のアルゴリズムです。これらの本では通常、階乗の再帰的な実装が示され、動作するが非常に遅く、スタック オーバーフローでクラッシュする可能性があるという警告が表示されます。懐疑的な人もいるが、再帰がアルゴリズムの中で最も強力なアイデアであるという事実には影響しない。

古典的な再帰階乗を見てみましょう。

階乗.c

 #include <stdio.h>
 int階乗( int n)
 {
 int前 = 0xdeadbeef;
 (n == 0 || n == 1)の場合{
 1 を返します。
 }
 前 = 階乗(n-1);
 n * previousを返します。
 }
 int main( int argc)
 {
 int答え = 階乗(5);
 printf( "%d\n" , 回答);
 } 
  

関数が自分自身を呼び出すという考え方は、最初は非常に不思議です。全体のプロセスを説明するために、次の図は、factorial(5)が呼び出され、n == 1の場合のスタックの構造を示しています。

factorial を呼び出すたびに、新しいスタック フレームが生成されます。これらのスタック フレームの作成と破棄により、再帰要素は反復部分よりも遅くなります。呼び出しが開始される前と戻る前にこれらのスタック フレームが蓄積されると、スタック領域が使い果たされ、プログラムがクラッシュする可能性があります。

しかし、こうした懸念は一般的に理論的なものである。たとえば、階乗スタック フレームはそれぞれ 16 バイトを占有します (これはスタックの配置やその他の要因によって異なる場合があります)。コンピュータで最新の x86 Linux カーネルを実行している場合、通常はデフォルトで 8 MB のスタック スペースがあるため、階乗 n は最大 512,000 を処理できます。これは非常に大きな数であり、表現するには 8,971,833 ビットを必要とするため、スタック スペースは問題になりません。小さな整数 (64 ビットであっても) は、スタック スペースがなくなる前に何万回もオーバーフローします。

CPU 使用率については後で説明しますが、今はビットやバイトから離れて、一般的な手法としての再帰について見てみましょう。私たちの階乗アルゴリズムは、整数 N、N-1、... 1 をスタックにプッシュし、それらを逆の順序で乗算することになります。プログラムの呼び出しスタックを使用してこれを行うための前提は、ヒープ上にスタックを割り当てて使用できることです。コール スタックには特別なプロパティがありますが、これは自由に使用できる別のデータ構造にすぎません。

コール スタックをデータ構造として見ると、別のことが理解できるようになります。つまり、すべての整数をそれ自体の前に追加し、それらをそれ自体で乗算することは、明らかに賢い考えではありません。 階乗を計算するには、反復プロセスを使用する方が合理的です。

伝統的な面接の質問に、迷路の中にネズミが置かれ、ネズミがチーズを見つけるのを手伝うというものがあります。ネズミは迷路の中で左または右に曲がることができると仮定します。この問題をどのようにモデル化して解決しますか?

人生におけるほとんどの問題と同様に、このげっ歯類の課題をグラフ、具体的にはノードが迷路内の位置を表すバイナリ ツリーに抽象化できます。次に、マウスをできるだけ左に移動し、行き止まりに達したら戻って右に曲がるようにします。次の図はマウスのパスを示しています。

各エッジ（線）は左または右に曲がることができ、マウスで選択できます。どちらかのターンがブロックされている場合、対応するエッジは存在しません。コール スタックを使用する場合でも、他のデータ構造を使用する場合でも、このプロセスは本質的に再帰的です。しかし、コールスタックの使用は非常に簡単です。

迷路.c

 #include <stdio.h>
 #include "maze.h"  
 int探索(maze_t *ノード)
 {
 int見つかった = 0;
 if (ノード == NULL ) {
 0を返します。
 }
 if (node->hasCheese) {
 return 1; // チーズが見つかった
 }
 見つかった = explore(node-> left ) || explore(node-> right );
戻り値が見つかりました。
 }
 int main( int argc)
 {
 int found = explore(&maze);
 }

maze.c:13 でチーズを見つけます。ここにスタックがあります。

ここで再帰を回避することは困難ですが、コール スタックを介して実行する必要があるわけではありません。たとえば、文字列 RRLL を使用してターンを追跡し、その文字列に基づいてマウスの次の動きを決定することができます。または、チーズ探しのステータスを記録するために他の変数を割り当てることもできます。再帰的な手順を実装していますが、独自のデータ構造を展開しています。

コールスタックがぴったり合うため、これはさらに複雑になる可能性があります。各スタック フレームには、現在のノードだけでなく、そのノードでの計算の状態も記録されます (この場合、左側のみを実行したか、右側を既に試したか)。しかし、私たちは溢れることを恐れて、良いものを諦めてしまうことがあります。それはとても愚かなことだと私は思います。

これまで見てきたように、スタックは大きく、スタック領域よりも先に他の制約が満たされることがよくあります。問題の大きさを確認し、安全に処理できるかどうかを確認することもできます。 CPU に対する恐怖は、主に、愚かな因子と、メモリのない信頼性の高い O(2n) 再帰フィボナッチという 2 つの広く見られる病理の例によって植え付けられます。これらは健全なスタック再帰アルゴリズムを表すものではありません。

実際には、スタック操作は高速です。データのオフセットは正確で、スタックはキャッシュ内にあり、コールド スタートは必要なく、ジョブを完了するための専用の命令があります。同時に、独自のヒープ割り当てデータ構造を使用すると、多くのオーバーヘッドが発生します。コールスタックの再帰よりも複雑でパフォーマンスの悪いものを書いている人がいるかもしれません。

最近の CPU は非常に優れており、通常はボトルネックにはなりません。多くの場合、シンプルさはパフォーマンスにつながります。