recursion c
古典的な例を使用して、C ++での再帰に関するすべてを調べます。
前のチュートリアルでは、C ++の関数について詳しく学びました。
関数を使用してコードをサブユニットに分解し、コードをより単純で読みやすくする以外に、関数は、リアルタイムの問題解決、数学および統計計算など、他のさまざまなアプリケーションで役立ちます。
C ++でより複雑なアプリケーションを開発するにつれて、多くの要件に遭遇するため、C ++のいくつかの特別な概念を使用する必要があります。再帰はそのような概念の1つです。
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
このチュートリアルでは、再帰について、再帰を実装するいくつかの古典的なC ++の例とともに、再帰が使用される場所と理由について詳しく学習します。
学習内容:
- 再帰とは何ですか?
- 再帰基本条件
- 再帰呼び出しのメモリ割り当て
- 再帰的なスタックオーバーフロー
- 直接再帰と間接再帰
- テール付きおよびテールなしの再帰
- 反復プログラミングに対する再帰の長所/短所
- 再帰の例
- 結論
- 推奨読書
再帰とは何ですか?
再帰は、関数がそれ自体を呼び出すプロセスです。再帰を実装するか、それ自体を呼び出す関数は、再帰関数と呼ばれます。再帰では、再帰関数はそれ自体を何度も呼び出し、終了条件が満たされるまで続行します。
次の画像は、再帰がどのように機能するかを示しています。
C ++で未定義の参照を修正する方法
上の図にあるように、メイン関数は関数funct()を呼び出します。次に、関数funct()は、その定義内でそれ自体を呼び出します。これが再帰の仕組みです。関数呼び出し自体のこのプロセスは、それを終了させる終了条件を提供するまで続きます。
通常、再帰を実装するときにコードブランチを提供し、再帰をトリガーする条件と通常の実行を実行する条件を提供します。
再帰基本条件
再帰が実行されると、ベースケースまたは終了ケースのソリューションが提供され、小さな問題のソリューションに基づいて、大きな問題のソリューションが構築されます。
再帰の典型的な例である階乗表記について考えてみましょう。。
数学的には、数nの階乗は次のとおりです。
n! = nxn-1x….x0!
その0を考えると! = 1;
したがって、n = 3の階乗は3になります! = 3×2!
3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6
したがって、プログラムでこの計算を次のように表すことができます。
int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }
したがって、上に示したように、階乗の上記の計算を再帰的な関数呼び出しに表現しました。数値nが1以下の場合、再帰呼び出しの代わりに1を返すことがわかります。これは、再帰を停止できる階乗の基本条件/ケースと呼ばれます。
したがって、基本条件は基本的に、再帰関数がそれ自体を呼び出す回数を決定します。これは、基本クラスに到達するまで、小さい数で表現することにより、大きい数の階乗を非常にうまく計算できることを意味します。
以下に示すのは、数値の階乗を計算するための完璧な例です。
#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout< 出力:
階乗を計算する数を入力します:10
10! = 3628800
上記の例では、再帰を実装しています。標準入力から階乗が見つかる数を取得し、それを階乗関数に渡します。
階乗関数では、基本条件を(n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.
再帰呼び出しのメモリ割り当て
関数呼び出しが行われると、呼び出し元の関数の状態がスタックに格納され、関数呼び出しが完了すると、プログラムが実行を継続できるようにその状態が復元されることがわかっています。
再帰関数呼び出しが行われると、呼び出された関数の状態またはメモリが呼び出し関数の状態の上に割り当てられ、再帰関数呼び出しごとにローカル変数の異なるコピーが作成されます。
基本条件に達すると、関数は呼び出し元の関数に戻り、メモリの割り当てが解除され、プロセスが続行されます。
再帰的なスタックオーバーフロー
再帰が無制限に続くと、スタックオーバーフローが発生する可能性があります。
このように再帰を続けることができるのはいつですか? 1つの状況は、基本条件を指定しない場合です。もう1つの状況は、プログラムの実行中に基本条件に達しない場合です。
例えば、上記の階乗プログラムを変更し、その基本条件を変更します。
int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }
上記のコードでは、基本条件を(n == 1000)に変更しました。ここで、数値n = 10を与えると、基本条件は決して到達しないと結論付けることができます。このようにして、ある時点で、スタック上のメモリが使い果たされ、スタックオーバーフローが発生します。
したがって、再帰プログラムを設計するときは、提供する基本条件に注意する必要があります。
直接再帰と間接再帰
これまでの再帰では、関数がそれ自体を呼び出すのを見てきました。これは直接再帰です。
別のタイプの再帰、つまり間接再帰があります。この場合、関数は別の関数を呼び出し、次にこの関数は呼び出し元の関数を呼び出します。 f1とf2が2つの関数の場合。次に、f1はf2を呼び出し、f2はf1を呼び出します。これは間接的な再帰です。
L 直接再帰を示すために階乗プログラムを改訂します。
#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout< 出力:
階乗を計算する数を入力してください:5
5! = 120
上記の例では、間接的な再帰を示しています。 main関数はfactorial_aを呼び出します。 Factorial_aはfactorial_bを呼び出します。次にfactorial_bはfactorial_aを呼び出します。プログラムの出力は影響を受けないことがわかります。
テール付きおよびテールなしの再帰
末尾の再帰関数は、関数内で最後の呼び出しが実行される再帰関数です。
例えば、次の関数を検討してください。
void display(int n){ if(n<=1) return; cout<<” ”<上記の例では、表示は最後の関数呼び出しであるような末尾の再帰関数です。
テール関数は、コンパイラーによって最適化できるため、非テール再帰関数よりも優れていると見なされます。その理由は、末尾の再帰呼び出しが関数の最後のステートメントであるため、この呼び出しの後に実行されるコードがないためです。
その結果、関数の現在のスタックフレームを保存する必要はありません。
反復プログラミングに対する再帰の長所/短所
再帰プログラムは、コンパクトでクリーンなコードを提供します。再帰プログラムは、プログラムを作成する簡単な方法です。階乗、フィボナッチ数列、ハノイの塔、樹木横断など、解決のために再帰を必要とする固有の問題がいくつかあります。
言い換えれば、それらは再帰によって効率的に解決されます。これらは、スタックまたは他のデータ構造を使用した反復プログラミングでも解決できますが、実装がより複雑になる可能性があります。
再帰的プログラミングと反復プログラミングの問題解決能力は同じです。ただし、再帰プログラムは、基本ケースが一致するまですべての関数呼び出しをスタックに格納する必要があるため、より多くのメモリスペースを必要とします。
再帰関数には、関数呼び出しと戻り値が多すぎるため、時間のオーバーヘッドもあります。
再帰の例
次に、再帰的プログラミングの例をいくつか実装します。
フィボナッチ数列
フィボナッチ数列は、次のように与えられるシーケンスです。
0 1 1 2 3 5 813……
上に示したように、フィボナッチ数列の最初の2つの数は0と1です。シーケンスの次の数は、前の2つの数の合計です。
Recursionを使用してこのシリーズを実装しましょう。
#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '< 出力:
フィボナッチ数列の要素数を入力してください:10
10個のフィボナッチ数列:0 1 1 2 3 5 8 13 21 34
この例では、再帰呼び出しを使用してフィボナッチ数列を生成しました。定数である最初の2つの数値が直接出力され、シーケンス内の次の数値には再帰関数を使用していることがわかります。
回文
回文数は、逆方向に読み取った場合、左から右方向に読み取った場合と同じ番号です。
例えば、 左から右へ、右から左へと読んでいるときの数字121は、同じ、つまり121を読みます。したがって、121は回文です。
数字291は、右から左に、つまり逆の順序で読むと、192のようになります。したがって、291は回文ではありません。
#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '< 出力:
回文を確認する番号を入力してください:6556
番号6556は回文です
同じもののスクリーンショットを以下に示します。
上記のプログラムでは、標準入力から入力番号を読み取ります。次に、この数値を再帰関数に渡して、数値の桁を逆にします。逆の数字と入力番号が同じである場合、その番号は回文です。
結論
これで、再帰は終了しました。このチュートリアルでは、再帰的プログラミング、再帰的機能、その長所/短所、およびさまざまな例を詳細に学習しました。
これらの例とは別に、再帰は、トラバーサル(インオーダー/プレオーダー/ポストオーダー)、ハノイの塔、BFSトラバーサルなどのいくつかの標準的な問題の解決にも使用されます。
=> ゼロからC ++を学ぶには、ここにアクセスしてください。
推奨読書