プログラマのための基本アルゴリズム: 再帰の説明

[[346111]]

序文

再帰は非常に重要なアルゴリズムの考え方です。フロントエンド開発者であっても、バックエンド開発者であっても、これを習得する必要があります。日常業務では、フォルダーのサイズをカウントしたり、XML ファイルを解析したりするために再帰アルゴリズムが必要です。これは非常に基本的かつ重要なため、面接官は面接中に再帰アルゴリズムを手作業で記述するように求めることがよくあります。この記事では、再帰アルゴリズムについて学びます〜

再帰とは何ですか?
再帰の特徴
再帰とスタックの関係
再帰的なアプリケーションシナリオ
再帰的な問題解決のアイデア
Leetcode ケース分析
再帰の考えられる問題と解決策

再帰とは何ですか?

コンピューターサイエンスにおける再帰とは、問題を類似のサブ問題に繰り返し分割することで問題を解決する方法を指します。簡単に言えば、再帰は関数が自分自身を呼び出すときに発生します。私は Zhihu で再帰の例を見ました。非常に鮮明だと思います。見てみましょう:

「再帰の最も適切な比喩は辞書を引くことです。私たちが使う辞書はそれ自体が再帰的です。単語を説明するには、より多くの単語が必要です。単語を調べると、その単語の説明にまだ理解できない単語があることに気づき、2 番目の単語を調べ始めます。残念ながら、2 番目の単語にもまだ理解できない単語があるため、3 番目の単語を調べます。これを繰り返し、説明を完全に理解できる単語が見つかるまで続けます。その後、再帰は終了し、後退し、以前に調べた単語を 1 つずつ理解し始め、最終的に最初の単語の意味を理解します。」 ❞

試しに、次のような再帰コードの例を見てみましょう。

公共 整数 合計( int n) {
    (n <= 1) の場合 {
 1 を返します。
    }
戻る 合計(n - 1) + n;
 }

再帰の特徴

実際、再帰には終了条件と自己呼び出しという 2 つの重要な機能があります。

自己呼び出し: 元の問題はサブ問題に分解できます。サブ問題と元の問題の解決方法は同じです。つまり、すべて同じ関数を呼び出します。
終了条件: 再帰には終了条件が必要です。つまり、無限ループ内で再帰自体を呼び出すことはできません。

上記のデモコード例と組み合わせて、再帰の特性を見てみましょう。

再帰とスタックの関係

実際、再帰プロセスはスタックに出入りするプロセスとして理解できます。この比喩は、読者が再帰をよりよく理解できるようにするためのものです。上記のコード例では、sum(n=3) のスタックダイアグラムを次のように計算します。

理解しやすくするために、次のように関数 sum(n=5) の再帰実行プロセスを見てみましょう。

sum(5)を計算する場合、最初にsum(5)がスタックにプッシュされ、次に元の問題sum(5)がサブ問題sum(4)に分割され、再びスタックにプッシュされます。これは、終了条件sum(n=1)=1に達するまで続き、その時点でスタックがポップされます。
sum(1)がスタックからポップされた後、sum(2)がポップされ始め、続いてsum(3)がポップされます。
最後に、sum(1)はLIFOであり、sum(5)はFIFOであるため、再帰プロセスはスタックの入出力プロセスとして理解できます。

再帰の典型的な応用シナリオ

再帰を使用して解決できる問題にはどのようなものがありますか? 言い換えると、再帰の一般的な適用シナリオは何ですか?

階乗問題
バイナリツリーの深さ
ハノイの塔問題
フィボナッチ数列
クイックソート、マージソート（分割統治アルゴリズムは再帰を体現する）
ファイルを走査し、xmlファイルを解析する

再帰的な問題解決のアイデア

再帰的な問題を解決するには、通常、次の 3 つのステップが必要です。

最初のステップは関数を定義することです
2番目のステップは再帰終了条件を見つけることです
2番目のステップは、再帰関数の同等の関係を推論することです。

この再帰的な問題解決方法は理解するのが少し抽象的なので、階乗再帰の例を見てみましょう。

1. 関数の機能を定義する

関数を定義するには、その関数が何を行うかを知る必要があります。言い換えれば、元の再帰問題が何であるかを知る必要があります。たとえば、階乗問題を解く必要がある場合、定義する関数は次のように n の階乗になります。

 //n の階乗 (n は 0 より大きい自然数)
 int階乗 ( int n){ 
 
 }

2. 再帰終了条件を見つける

再帰の典型的な特徴は、終了条件が存在する必要があることです。つまり、無限ループ内で再帰自体を呼び出すことはできません。したがって、再帰的な思考を使用して問題を解決する場合は、再帰の終了条件が何であるかを調べる必要があります。たとえば、階乗問題では、n=1 の場合、それ以上再帰する必要がなく、ループから抜け出すことができます。次のように、n=1 を再帰の終了条件として使用できます。

 //n の階乗 (n は 0 より大きい自然数)
 int階乗 ( int n){
    (n==1)の場合{
 1 を返します。
    }
 }

3. 再帰関数の同値関係

再帰の「本来の意味」は、元の問題を類似した、より解決しやすいサブ問題に分解できること、つまり「元の問題とサブ問題が同じ関数関係で表現できること」です。再帰関数の等価関係式は、元の問題とサブ問題の関係を見つけ、その関数をいかにして明確に数式で表現するかということに等価です。階乗の式は f(n) = n * f(n-1) と表すことができるため、再帰階乗プログラムコードは次のように記述できます。

 int階乗 ( int n){
    (n==1)の場合{
 1 を返します。
    }
 n * 階乗(n-1)を返します。
 }

「注意してください」、再帰関数の同値関係はすべて階乗のように単純で、すぐに導出できるわけではありません。もっと触れて、もっと蓄積して、もっと考えて、もっと再帰的な質問を練習する必要があります〜

Leetcode ケース分析

典型的な LeetCode の再帰質問を分析してみましょう。

❝元の質問のリンクはこちらです: https://leetcode-cn.com/problems/invert-binary-tree/❞

「質問：」二分木を反転します。

入力：

出力：

私たちは、上記の再帰的な問題解決の 3 つのトリックに従います。

「1. 関数を定義する」

関数 function (つまり、元の再帰問題) はツリーを与えてそれを反転することなので、関数は次のように定義できます。

 // バイナリツリーを反転する
パブリックTreeNode invertTree(TreeNode ルート) {
 } 
 
 /**
 *バイナリツリーノードの定義。
 *パブリッククラス TreeNode {
 *整数値;
 * TreeNode左;
 * TreeNode右;
 * ツリーノード( int x) { val = x; }
 * }
 */

「2. 再帰終了条件を見つける」

このツリーを反転する必要がないのはどのような場合でしょうか? もちろん、現在のノードが null の場合、または現在のノードがリーフノードである場合です。したがって、終了条件を追加すると次のようになります。

 // バイナリツリーを反転する
パブリックTreeNode invertTree(TreeNode ルート) {
    if(root== null || (root.left == null && root.right == null ) ){
ルートを返します。
    }
 }

「3. 再帰関数の同値関係」

元々の問題は、ツリーを反転することです。これをサブ問題に分割して、それぞれ左のサブツリーと右のサブツリーを反転することはできますか? 左のサブツリーを反転するというサブ問題は、左のサブツリーの左のサブツリーと左のサブツリーの右のサブツリーを反転することに分割できますか? 次に、リーフノードに到達するまで反転を続けます。まあ、理解するには写真を見てください。

まず、ルートノードが 4 のツリーを反転する場合、「その左のサブツリー (ルートノードは 2) と右のサブツリー (ルートノードは 7) を反転」する必要があります。これは再帰的なプロセスです。

次に、ルートノード 2 を持つツリーはリーフノードではないため、「左のサブツリー (ルートノードは 1) と右のサブツリー (ルートノードは 3) を反転」し続ける必要があります。ノード 1 と 3 は両方とも「リーフノード」であるため、返されます。これも再帰的なプロセスです。

同様に、ルートノード 7 を持つツリーはリーフノードではないため、左のサブツリー (ルートノード 6) と右のサブツリー (ルートノード 9) を反転する必要があります。ノード 6 と 9 はリーフノードなので、これらも返されます。

左のサブツリー（ルートノードは2）と右のサブツリー（ルートノードは7）を反転した後、これらのステップは「返される」、つまり再帰的な戻りプロセスとなり、ツリーを反転するタスクが完了します。

明らかに、再帰関係は次のようになります。

 invertTree(root) = invertTree(root.left ) + invertTree(root.right ) ;

したがって、次のコードを簡単に導き出すことができます。

 // バイナリツリーを反転する
パブリックTreeNode invertTree(TreeNode ルート) {
    if(root== null || (root.left == null && root.right == null ) {
ルートを返します。
    }
    //左のサブツリーを反転する
    TreeNode のleft = invertTree ( root.left );
    //右のサブツリーを反転する
    TreeNode を右に反転します( root.right )。
 }

ここでのコードでは、注意する必要があることが 1 つあります。ツリーの左と右のサブツリーを反転した後、左と右のサブツリーの参照位置も入れ替える必要があります。

ルート.left = right ;
 ルート.right =左;

したがって、Leetcode におけるこの古典的な再帰的質問の「最終的な解決コード」は次のようになります。

クラスソリューション{
パブリックTreeNode invertTree(TreeNode ルート) {
         if(root== null || (root.left == null && root.right == null ) ){
ルートを返します。
         }
         //左のサブツリーを反転する
         TreeNode のleft = invertTree ( root.left );
         //右のサブツリーを反転する
         TreeNode を右に反転します( root.right )。
         //左と右のサブツリーを入れ替える~
         ルート.left = right ;
         ルート.right =左;
ルートを返します。
    }
 }

最終的なソリューションコードをLeetCodeに送信すれば合格します〜

再帰の問題

再帰呼び出しレベルが多すぎるとスタックオーバーフローが発生します
再帰的かつ繰り返しの計算は効率を低下させる

スタックオーバーフロー問題

各関数呼び出しはメモリスタックにスペースを割り当て、各プロセスのスタック容量は制限されます。
再帰呼び出しのレベルが多すぎると、スタック容量を超え、呼び出しスタックのオーバーフローが発生します。
実際、前のセクションで説明したように、再帰プロセスはスタックのポップとプッシュに似ています。再帰の回数が多すぎると、スタックの深さをさらに深くする必要があり、最終的にはスタック容量が本当に足りなくなります。

「コード例は次のとおりです。」

 /**
 * 再帰スタックオーバーフローテスト
 */
パブリッククラスRecursionTest { 
 
公共 静的void main(String[] args) {
合計（50000）;
    }
    プライベートスタティック 整数 合計( int n) {
        (n <= 1) の場合 {
 1 を返します。
        }
戻る 合計(n - 1) + n;
    }
 }

「ランニング結果:」

スレッド「main」で例外が発生しました。java.lang.StackOverflowError が recursion.RecursionTest.sum(RecursionTest.java:13) で発生しました。

このスタックオーバーフローの問題を解決するにはどうすればよいでしょうか。まず、「再帰を最適化する」必要があります。本当に何度も再帰的に呼び出す必要がありますか。本当に必要な場合は、まず「JVM スタックスペースメモリを増やす」ことを少し試してください。それでも問題が解決しない場合は、再帰を放棄して「他のソリューションに最適化する」必要があります。

繰り返し計算を行うとプログラム効率が低下する

古典的なカエルのジャンプ問題を見てみましょう。カエルは一度に 1 段ずつジャンプすることも、一度に 2 段ずつジャンプすることもできます。カエルが n 段の階段をジャンプして上る方法が何通りあるか調べます。

ほとんどの読者は、この問題を解決するために次の再帰コードを簡単に思いつくでしょう。

クラスソリューション{
公共  int numWays( int n) {
    (n == 0)の場合{
 1 を返します。
     }
    (n <= 2)の場合{
 nを返します。
    }
 numWays(n-1) + numWays(n-2)を返します。
    }
 }

しかし、LeetCode に提出したところ、問題が発生しました。制限時間を超過してしまったのです。

なぜタイムアウトしたのでしょうか? 再帰に時間がかかっているのはどこでしょうか? まず「再帰ツリー」を描いてみましょう:

元の問題f(10)を解くには、まずサブ問題f(9)とf(8)を解く必要がある。

次にf(9)を計算するには、まずサブ問題f(8)とf(7)を計算する必要があります。

再帰ツリーはf(2)とf(1)に到達すると終了します。

まず、この再帰の時間計算量を見てみましょう。「再帰の時間計算量 = サブ問題を解く時間 * サブ問題の数」

1つのサブ問題の所要時間 = f(n-1)+f(n-2) は加算演算なので、複雑さは「O(1)」です。
質問数 = 再帰ツリーノードの総数、再帰ツリーの要約ポイント = 2^n-1 なので、複雑さは「O(2^n)」です。

したがって、カエルスキップ再帰ソリューションの時間計算量は O(1) * O(2^n) = O(2^n) となり、指数関数的かつ爆発的な増加となります。「n が比較的大きい場合、タイムアウトは正常です。」

振り返って、この再帰ツリーをよく見ると、「繰り返し計算が多数」あることがわかります。たとえば、f(8) は 2 回計算され、f(7) は 3 回計算されます...つまり、この再帰アルゴリズムが非効率な理由は、繰り返し計算が多数あることです。

「それで、この問題をどうやって解決すればいいのでしょうか？」

繰り返し計算が多いので、まず計算結果を保存、つまりメモを作成します。次回必要になったときに、「メモ」で確認できます。メモがある場合は直接取得できます。メモがない場合は、再度計算できます。このようにして、繰り返し計算する時間を節約できます。これが「メモ付き解法」です。

メモ化による再帰的なソリューションを見てみましょう〜

一般的に、この「メモ」としては配列やハッシュマップが使用されます。

f(10)の解が「memo」で追加されたと仮定して、再帰ツリーをもう一度描画してみましょう。

「ステップ1」、f(10) = f(9) + f(8)、次のようにf(9)とf(8)の両方を計算してメモに追加する必要があります。

「ステップ2」、f(9) = f(8) + f(7)、f(8) = f(7) + f(6)、f(8)はすでにメモにあるので省略できます。f(7)とf(6)を計算してメモに追加する必要があります。

「ステップ3」、f(8) = f(7) + f(6)では、f(8)、f(7)、f(6)はすべてメモに記載されているので、すべて切り取ることができます。

したがって、メモ再帰アルゴリズムを使用すると、再帰ツリーは次のように裸のツリートランクになります。

「メモ」を使用した再帰アルゴリズムの場合、サブ問題の数 = ツリーノードの数 = n であり、サブ問題の解決は依然として O(1) であるため、「メモ」を使用した再帰アルゴリズムの時間計算量は O(n) です。次に、「memo」を使用した再帰アルゴリズムを使用して、カエルのステップ問題のタイムアウト問題をコーディングして解決します。コードは次のとおりです。

パブリッククラスソリューション{
    //ハッシュマップをメモとして使用
    Map< Integer , Integer > tempMap = new HashMap();
公共  int numWays( int n) {
        // n = 0 も 1 型としてカウントされます
        (n == 0)の場合{
 1 を返します。
        }
        (n <= 2) の場合 {
 nを返します。
        }
        //まず計算されたかどうか、つまりメモが
        tempMap.containsKey(n) の場合 {
            //メモが存在する、つまり計算済みなので、直接返す
tempMap.get(n)を返します。
        }それ以外{
            // メモなし、つまり計算なし、再帰計算を実行し、結果を 1000000007 を法としてメモ マップに保存します (これは LeetCode の質問で必須です)
            tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
 tempMap.get(n)を返します。
        }
    }
 }