再帰の概要 – データ構造とアルゴリズムのチュートリアル
再帰とは何ですか?
関数がそれ自体を直接または間接的に呼び出すプロセスは再帰と呼ばれ、対応する関数は再帰関数と呼ばれます。再帰アルゴリズムを使用すると、特定の問題を非常に簡単に解決できます。そのような問題の例としては、 ハノイの塔 (TOH) 、 インオーダー/プレオーダー/ポストオーダーのツリートラバーサル 、DFS of Graph など。再帰関数は、それ自体のコピーを呼び出し、元の問題のより小さな部分問題を解決することによって、特定の問題を解決します。必要に応じて、さらに多くの再帰呼び出しを生成できます。この再帰プロセスを終了するには、特定のケースを提供する必要があることを知っておくことが重要です。したがって、関数がそれ自体を呼び出すたびに、元の問題のより単純なバージョンを使用すると言えます。
再帰の必要性
再帰は、コードの長さを短縮し、読み書きを容易にする素晴らしいテクニックです。これには、後で説明する反復手法に比べて特定の利点があります。同様のサブタスクとともに定義できるタスクである再帰は、そのための最良のソリューションの 1 つです。例えば;数値の階乗。
再帰のプロパティ:
- 異なる入力で同じ操作を複数回実行する。
- すべてのステップで、問題を小さくするために入力を小さくしてみます。
- 再帰を停止するには基本条件が必要です。そうしないと無限ループが発生します。
アルゴリズム: ステップ
The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.
数学的解釈
プログラマが最初の n 個の自然数の合計を求めなければならないという問題を考えてみましょう。これを行うにはいくつかの方法がありますが、最も簡単なアプローチは、単純に 1 から n までの数値を加算することです。したがって、関数は単純に次のようになります。
アプローチ(1) – 単純に 1 つずつ追加する
f(n) = 1 + 2 + 3 +……..+ n
しかし、これを表す別の数学的アプローチがあります。
アプローチ(2) – 再帰的追加
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
アプローチ (1) とアプローチ (2) の間には単純な違いがあります。 アプローチ(2) 関数 f() それ自体は関数内で呼び出されるため、この現象は再帰と呼ばれ、再帰を含む関数は再帰関数と呼ばれます。結局のところ、これはプログラマーがいくつかの問題をより簡単かつ効率的にコーディングするための優れたツールです。方法。
再帰関数はどのようにメモリに保存されるのでしょうか?
再帰関数は再帰呼び出しごとにスタックに追加し、呼び出しが終了するまでスタックに値を保持するため、再帰ではより多くのメモリが使用されます。再帰関数はスタックデータ構造と同様にLIFO(LAST IN FIRST OUT)構造を使用します。 スタックデータ構造/
再帰の基本条件は何ですか?
再帰的プログラムでは、基本ケースの解決策が提供され、より大きな問題の解決策はより小さな問題の観点から表現されます。
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); } 上の例では、n <= 1 の基本ケースが定義されており、基本ケースに達するまで数値の大きい値を小さい値に変換することで解決できます。
再帰を使用して特定の問題をどのように解決するのでしょうか?
この考え方は、問題を 1 つまたは複数の小さな問題の観点から表現し、再帰を停止する 1 つまたは複数の基本条件を追加することです。たとえば、(n-1) の階乗がわかっている場合は、階乗 n を計算します。階乗の基本ケースは n = 0 です。n = 0 の場合は 1 を返します。
再帰でスタック オーバーフロー エラーが発生するのはなぜですか?
基本ケースに達していない場合、または定義されていない場合は、スタック オーバーフローの問題が発生する可能性があります。これを理解するために例を挙げてみましょう。
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); } ファクト(10) が呼び出されると、ファクト(9)、ファクト(8)、ファクト(7) などが呼び出されますが、数値が 100 に達することはありません。したがって、基本ケースには達しません。これらの関数によってスタック上のメモリが使い果たされると、スタック オーバーフロー エラーが発生します。
直接再帰と間接再帰の違いは何ですか?
関数 fun が同じ関数 fun を呼び出す場合、その関数は直接再帰的と呼ばれます。関数 fun が別の関数 (fun_new など) を呼び出し、fun_new が直接または間接的に fun を呼び出す場合、その関数は間接再帰的と呼ばれます。直接再帰と間接再帰の違いを表 1 に示します。
// An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... } 尾部再帰と非尾部再帰の違いは何ですか?
再帰呼び出しが関数によって最後に実行される場合、再帰関数は末尾再帰となります。ご参照ください 末尾再帰の記事 詳細については。
再帰でさまざまな関数呼び出しにメモリがどのように割り当てられるのでしょうか?
main() から関数が呼び出されると、メモリがスタック上でその関数に割り当てられます。再帰関数はそれ自体を呼び出し、呼び出された関数のメモリは呼び出し元の関数に割り当てられたメモリの上に割り当てられ、関数呼び出しごとにローカル変数の異なるコピーが作成されます。基本ケースに達すると、関数は呼び出し元の関数に値を返し、メモリの割り当てが解除されてプロセスが続行されます。
単純な関数を使用して、再帰がどのように機能するかを例に挙げてみましょう。
CPP
// A C++ program to demonstrate working of> // recursion> #include> using> namespace> std;> > void> printFun(> int> test)> {> > if> (test <1)> > return> ;> > else> {> > cout < < test < <> ' '> ;> > printFun(test - 1);> // statement 2> > cout < < test < <> ' '> ;> > return> ;> > }> }> > // Driver Code> int> main()> {> > int> test = 3;> > printFun(test);> }> |
ジャワ
// A Java program to demonstrate working of> // recursion> class> GFG {> > static> void> printFun(> int> test)> > {> > if> (test <> 1> )> > return> ;> > else> {> > System.out.printf(> '%d '> , test);> > printFun(test -> 1> );> // statement 2> > System.out.printf(> '%d '> , test);> > return> ;> > }> > }> > > // Driver Code> > public> static> void> main(String[] args)> > {> > int> test => 3> ;> > printFun(test);> > }> }> > // This code is contributed by> // Smitha Dinesh Semwal> |
Python3
# A Python 3 program to> # demonstrate working of> # recursion> > > def> printFun(test):> > > if> (test <> 1> ):> > return> > else> :> > > print> (test, end> => ' '> )> > printFun(test> -> 1> )> # statement 2> > print> (test, end> => ' '> )> > return> > # Driver Code> test> => 3> printFun(test)> > # This code is contributed by> # Smitha Dinesh Semwal> |
C#
// A C# program to demonstrate> // working of recursion> using> System;> > class> GFG {> > > // function to demonstrate> > // working of recursion> > static> void> printFun(> int> test)> > {> > if> (test <1)> > return> ;> > else> {> > Console.Write(test +> ' '> );> > > // statement 2> > printFun(test - 1);> > > Console.Write(test +> ' '> );> > return> ;> > }> > }> > > // Driver Code> > public> static> void> Main(String[] args)> > {> > int> test = 3;> > printFun(test);> > }> }> > // This code is contributed by Anshul Aggarwal.> |
PHP
// PHP program to demonstrate // working of recursion // function to demonstrate // working of recursion function printFun($test) { if ($test <1) return; else { echo('$test '); // statement 2 printFun($test-1); echo('$test '); return; } } // Driver Code $test = 3; printFun($test); // This code is contributed by // Smitha Dinesh Semwal. ?>>> |
JavaScript
> > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> > {> > if> (test <1)> > return> ;> > else> {> > document.write(test +> ' '> );> > printFun(test - 1);> // statement 2> > document.write(test +> ' '> );> > return> ;> > }> > }> > // Driver code> > let test = 3;> > printFun(test);> > > |
出力
3 2 1 1 2 3
時間計算量: ○(1)
補助スペース: ○(1)
いつ プリントファン(3) main() から呼び出され、メモリが割り当てられます。 プリントファン(3) 次の図に示すように、ローカル変数 test が 3 に初期化され、ステートメント 1 ～ 4 がスタックにプッシュされます。最初に「3」が出力されます。ステートメント 2 では、 プリントファン(2) が呼び出され、メモリが割り当てられます プリントファン(2) ローカル変数 test は 2 に初期化され、ステートメント 1 ～ 4 がスタックにプッシュされます。同様に、 プリントファン(2) 電話をかける プリントファン(1) そして プリントファン(1) 電話をかける プリントファン(0) 。 プリントファン(0) if ステートメントに進み、次に戻ります プリントファン(1) 。残りの発言は、 プリントファン(1) が実行され、に戻ります プリントファン(2) 等々。出力では、3 ～ 1 の値が出力され、次に 1 ～ 3 が出力されます。メモリスタックは以下の図に示されています。
再帰と反復
| SRNo. | 再帰 | 反復 |
| 1) | 基本ケースが true になると終了します。 | 条件が偽になると終了します。 |
| 2) | 関数と一緒に使用されます。 | ループと一緒に使用します。 |
| 3) | すべての再帰呼び出しには、スタック メモリ内に追加のスペースが必要です。 | すべての反復では余分なスペースは必要ありません。 |
| 4) | コードサイズが小さくなります。 | コードサイズが大きくなります。 |
ここで、再帰を使用して解決できるいくつかの実際的な問題について説明し、その基本的な動作を理解しましょう。基本的な理解については、次の記事をお読みください。
再帰の基本的な理解。
問題 1: n>2 の n のフィボナッチ数列を求めるプログラムと漸化式を作成します。
数学の方程式:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;
再発関係:
T(n) = T(n-1) + T(n-2) + O(1)
再帰的プログラム:
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3
実装：
C++
// C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(> int> n)> > > // Driver Code> int> main()> {> > // Initialize variable n.> > int> n = 5;> > cout < <> 'Fibonacci series of 5 numbers is: '> ;> > > // for loop to print the fibonacci series.> > for> (> int> i = 0; i { cout <' '; } return 0; }> |
C
// C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(> int> n)> > > // Stop condition> > if> (n == 0)> > return> 0;> > > // Stop condition> > if> (n == 1> > // Driver Code> int> main()> {> > // Initialize variable n.> > int> n = 5;> > printf> (> 'Fibonacci series '> > 'of %d numbers is: '> ,> > n);> > > // for loop to print the fibonacci series.> > for> (> int> i = 0; i printf('%d ', fib(i)); } return 0; }> |
ジャワ
// Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(> int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > > // Initialize variable n.> > int> n => 5> ;> > System.out.print(> 'Fibonacci series of 5 numbers is: '> );> > > // for loop to print the fibonacci series.> > for> (> int> i => 0> ; i { System.out.print(fib(i)+' '); } } } // This code is contributed by rutvik_56.> |
Python3
# Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > > # Stop condition> > if> (n> => => 0> ):> > return> 0> > > # Stop condition> > if> (n> => => 1> or> n> => => 2> ):> > return> 1> > > # Recursion function> > else> :> > return> (fib(n> -> 1> )> +> fib(n> -> 2> ))> > > # Driver Code> > # Initialize variable n.> n> => 5> ;> print> (> 'Fibonacci series of 5 numbers is :'> ,end> => ' '> )> > # for loop to print the fibonacci series.> for> i> in> range> (> 0> ,n):> > print> (fib(i),end> => ' '> )> |
C#
using> System;> > public> class> GFG> {> > > // Function for fibonacci> > static> int> fib(> int> n)> > n == 2)> > return> 1;> > > // Recursion function> > else> > return> (fib(n - 1) + fib(n - 2));> > > > > // Driver Code> > static> public> void> Main ()> > {> > > // Initialize variable n.> > int> n = 5;> > Console.Write(> 'Fibonacci series of 5 numbers is: '> );> > > // for loop to print the fibonacci series.> > for> (> int> i = 0; i { Console.Write(fib(i) + ' '); } } } // This code is contributed by avanitrachhadiya2155> |
JavaScript
> // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)> n == 2)> > return> 1;> > // Recursion function> > else> > return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(> 'Fibonacci series of 5 numbers is: '> );> > // for loop to print the fibonacci series.> for> (let i = 0; i { document.write(fib(i) + ' '); }> |
出力
Fibonacci series of 5 numbers is: 0 1 1 2 3
時間計算量: O(2 n )
補助スペース: の上）
これは、入力 5 の再帰ツリーです。これは、大きな問題を小さな問題に解決する方法を明確に示しています。
fib(n) はフィボナッチ関数です。特定のプログラムの時間計算量は、関数呼び出しによって異なります。
fib(n) -> レベル CBT (UB) -> 2^n-1 ノード -> 2^n 関数呼び出し -> 2^n*O(1) -> T(n) = O(2^n)
ベストケースの場合。
T(n) = ?(2^n2)
働く：
問題 2: n>2 の n の階乗を求めるプログラムと漸化式を作成します。
数学の方程式:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>>再発関係:
// C++ code to implement factorial>#include>using>namespace>std;>>// Factorial function>int>f(>int>n)>n == 1)>>return>1;>>>// Recursive condition>>else>>return>n * f(n - 1);>>>// Driver code>int>main()>{>>int>n = 5;>>cout < <>'factorial of '><' is: ' < return 0; }>
C
// C code to implement factorial>#include>>// Factorial function>int>f(>int>n)>>>// Stop condition>>if>(n == 0>>// Driver code>int>main()>{>>int>n = 5;>>printf>(>'factorial of %d is: %d'>, n, f(n));>>return>0;>}>
ジャワ
// Java code to implement factorial>public>class>GFG>{>>>// Factorial function>>static>int>f(>int>n)>>>>>// Driver code>>public>static>void>main(String[] args)>>{>>int>n =>5>;>>System.out.println(>'factorial of '>+ n +>' is: '>+ f(n));>>}>}>>// This code is contributed by divyesh072019.>
Python3
# Python3 code to implement factorial>># Factorial function>def>f(n):>>># Stop condition>>if>(n>=>=>0>or>n>=>=>1>):>>return>1>;>>># Recursive condition>>else>:>>return>n>*>f(n>->1>);>>># Driver code>if>__name__>=>=>'__main__'>:>>>n>=>5>;>>print>(>'factorial of'>,n,>'is:'>,f(n))>>># This code is contributed by pratham76.>
C#
// C# code to implement factorial>using>System;>class>GFG {>>>// Factorial function>>static>int>f(>int>n)>>n == 1)>>return>1;>>>// Recursive condition>>else>>return>n * f(n - 1);>>>>>// Driver code>>static>void>Main()>>{>>int>n = 5;>>Console.WriteLine(>'factorial of '>+ n +>' is: '>+ f(n));>>}>}>>// This code is contributed by divyeshrabadiya07.>
JavaScript
>// JavaScript code to implement factorial>>// Factorial function>function>f(n)>n == 1)>>return>1;>>>// Recursive condition>>else>>return>n*f(n-1);>>>// Initialize variable n.>let n = 5;>document.write(>'factorial of '>+ n +>' is: '>+ f(n));>>// This code is contributed by probinsah.>>
出力
factorial of 5 is: 120時間計算量: の上）
補助スペース: の上）働く：
ユーザー入力に対する階乗再帰関数の図 5.
例: 実際の問題における再帰の実際の応用
再帰は、コンピュータ サイエンスやプログラミングに多くの用途がある強力な手法です。再帰の一般的な応用例をいくつか示します。
ツリーとグラフの走査 : 再帰は、ツリーやグラフなどのデータ構造の走査と検索によく使用されます。再帰アルゴリズムを使用すると、ツリーまたはグラフのすべてのノードまたは頂点を系統的に調査できます。並べ替えアルゴリズム : 再帰的アルゴリズムは、クイックソートやマージ ソートなどの並べ替えアルゴリズムでも使用されます。これらのアルゴリズムは再帰を使用してデータを小さなサブ配列またはサブリストに分割し、それらを並べ替えてから、それらを再びマージします。分割統治アルゴリズム : 二分探索アルゴリズムなど、分割統治アプローチを使用する多くのアルゴリズムは、再帰を使用して問題を小さな部分問題に分割します。フラクタル生成 : 再帰アルゴリズムを使用して、フラクタルの形状とパターンを生成できます。たとえば、マンデルブロ集合は、複素数に再帰公式を繰り返し適用することによって生成されます。バックトラッキング アルゴリズム : バックトラッキング アルゴリズムは、各決定が前の決定に依存する一連の決定を伴う問題を解決するために使用されます。これらのアルゴリズムは、再帰を使用して実装でき、すべての可能なパスを探索し、解決策が見つからない場合はバックトラックできます。メモ化 : メモ化は、高コストの関数呼び出しの結果を保存し、同じ入力が再度発生したときにキャッシュされた結果を返すことを含む技術です。メモ化は、部分問題の結果を計算してキャッシュする再帰関数を使用して実装できます。
これらは、コンピューター サイエンスとプログラミングにおける再帰の多くの応用例のほんの一例にすぎません。再帰は、さまざまな種類の問題を解決するために使用できる多用途かつ強力なツールです。
説明: 再帰の実例の 1 つ:
再帰は、関数自体を呼び出すプログラミング手法です。これは複雑な問題を解決するための強力なツールですが、無限ループやスタック オーバーフローを避けるために慎重な実装も必要です。
Python で再帰を実装する例を次に示します。
C++
#include>using>namespace>std;>int>factorial(>int>n)>{>>>// Base case: if n is 0 or 1, return 1>>if>(n == 0 || n == 1) {>>return>1;>>}>>>// Recursive case: if n is greater than 1,>>// call the function with n-1 and multiply by n>>else>{>>return>n * factorial(n - 1);>>}>}>>int>main()>{>>>// Call the factorial function and print the result>>int>result = factorial(5);>>cout < < result
ジャワ
import>java.util.*;>>class>Main {>>public>static>int>factorial(>int>n)>>{>>// Base case: if n is 0 or 1, return 1>>if>(n ==>0>|| n ==>1>) {>>return>1>;>>}>>>// Recursive case: if n is greater than 1,>>// call the function with n-1 and multiply by n>>else>{>>return>n * factorial(n ->1>);>>}>>}>>>public>static>void>main(String[] args)>>{>>// Call the factorial function and print the result>>int>result = factorial(>5>);>>System.out.println(result);>// Output: 120>>}>}>
Python3
def>factorial(n):>># Base case: if n is 0 or 1, return 1>>if>n>=>=>0>or>n>=>=>1>:>>return>1>>># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n>>else>:>>return>n>*>factorial(n>->1>)>># Call the factorial function and print the result>result>=>factorial(>5>)>print>(result)># Output: 120>
C#
using>System;>>class>MainClass {>>public>static>int>factorial(>int>n)>>{>>// Base case: if n is 0 or 1, return 1>>if>(n == 0 || n == 1) {>>return>1;>>}>>>// Recursive case: if n is greater than 1,>>// call the function with n-1 and multiply by n>>else>{>>return>n * factorial(n - 1);>>}>>}>>>public>static>void>Main (>string>[] args) {>>// Call the factorial function and print the result>>int>result = factorial(5);>>Console.WriteLine(result);>// Output: 120>>}>}>
JavaScript
function>factorial(n) {>>// Base case: if n is 0 or 1, return 1>>if>(n === 0 || n === 1) {>>return>1;>>}>>>// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n>>else>{>>return>n * factorial(n - 1);>>}>}>>// Call the factorial function and print the result>const result = factorial(5);>console.log(result);>// Output: 120>
出力
120この例では、整数 n を入力として受け取る、factorial という関数を定義します。この関数は再帰を使用して n の階乗 (つまり、n までのすべての正の整数の積) を計算します。
階乗関数はまず、n が 0 または 1 (基本ケース) であるかどうかを確認します。 n が 0 または 1 の場合、関数は 0 なので 1 を返します。そして1！は両方とも 1 です。
n が 1 より大きい場合、関数は再帰的ケースに入ります。 n-1 を引数として自分自身を呼び出し、結果を n 倍します。これにより n が計算されます。 (n-1)! を再帰的に計算することによって。
再帰は慎重に使用しないと非効率的であり、スタック オーバーフローを引き起こす可能性があることに注意することが重要です。関数呼び出しごとに呼び出しスタックに新しいフレームが追加されるため、再帰が深すぎるとスタックが大きくなりすぎる可能性があります。さらに、再帰では複数レベルの関数呼び出しについて考える必要があるため、コードの理解とデバッグがさらに困難になる可能性があります。
ただし、再帰は、複雑な問題、特に問題を小さなサブ問題に分割する問題を解決するための強力なツールにもなり得ます。再帰を正しく使用すると、コードがより洗練され、読みやすくなります。
反復プログラミングと比較した再帰プログラミングの欠点は何ですか?
再帰的プログラムと反復的プログラムはどちらも同じ問題解決能力を持っていることに注意してください。つまり、すべての再帰的プログラムは反復的に作成でき、その逆もまた同様です。再帰的プログラムは、基本ケースに達するまですべての関数がスタック内に残るため、反復的プログラムよりも多くのスペースを必要とします。また、関数呼び出しと戻り値のオーバーヘッドのため、所要時間も長くなります。さらに、コードの長さが短いため、コードを理解するのが難しく、コードを記述する際には特別な注意が必要です。再帰呼び出しが適切にチェックされないと、コンピュータのメモリが不足する可能性があります。
反復プログラミングと比較した再帰プログラミングの利点は何ですか?
再帰は、コードを記述するためのクリーンで簡単な方法を提供します。一部の問題はツリートラバーサルのように本質的に再帰的です。 ハノイの塔 このような問題に対しては、再帰的なコードを記述することが推奨されます。スタック データ構造を利用して、このようなコードを反復的に記述することもできます。たとえば、「Inorder Tree Traversal without Recursion」、「Iterative Tower of Hanoi」を参照してください。再帰の概要:
- 再帰には 2 種類のケース、つまり再帰ケースと基本ケースがあります。
- 基本ケースは、ケースが true であることが判明した場合に再帰関数を終了するために使用されます。
- 再帰呼び出しごとに、スタック メモリ内にそのメソッドの新しいコピーが作成されます。
- 無限再帰によりスタック メモリが不足する可能性があります。
- 再帰的アルゴリズムの例: マージ ソート、クイック ソート、ハノイの塔、フィボナッチ数列、階乗問題など。
初心者向けの出力ベースの練習問題:
再帰の練習問題 |セット1
再帰の練習問題 |セット2
再帰の練習問題 |セット3
再帰の練習問題 |セット4
再帰の練習問題 |セット5
再帰の練習問題 |セット6
再帰の練習問題 |セット 7
再帰に関するクイズ
再帰に関するコーディングの実践:
再帰に関するすべての記事
再帰的練習問題と解答
