再帰 -1

はじめに 1

関数がそれ自体を呼び出すプロセスは再帰と呼ばれ、
対応する関数は再帰関数と呼ばれます。
コンピュータープログラミングは数学の基本的な応用なので、
をやってみましょう。 まず、再帰の背後にある数学的推論を理解しようとします。
一般に、関数の概念は誰もが知っています。一言で言えば、関数は
です。 入力を与えると出力を生成する数式。例:
関数 F(x) が次のように定義される関数であるとします: F(x) = x^2 + 4
この関数の Java コードは次のように記述できます:

パブリック 静的 int F(int x){
return (x * x + 4);
}

これで、x のさまざまな値をこの関数に渡して、出力を受け取ることができます
それに応じて。
再帰に進む前に、別の数学を理解してみましょう
数学的帰納法 (PMI) として知られる概念。

数学的帰納法 (PMI) は、ステートメントを証明するためのテクニックです。
式、または自然数の集合について主張される定理。
があります 次の 3 つのステップ:
1.** 自明なケースのステップ*: このステップでは、
の目的のステートメントを証明します。 n = 0 または n = 1 のような基本ケース。
2.* 仮定のステップ**: このステップでは、目的のステートメント
を仮定します。 は n = k に対して有効です。

1. ステップを証明する: 仮定ステップの結果から、次のことを証明します。 n = k が true である場合は常に、目的の方程式に対して n = k + 1 も当てはまります。

例: 数学的帰納法原理を使用して次のことを証明してみましょう:
S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(最初の N 個の自然数の合計)
証明:
ステップ 1: N = 1 の場合、S(1) = 1 が真です。
ステップ 2: 与えられたステートメントが N = k に対して真であると仮定します。つまり、
1 + 2 + 3 + .... + k = (k * (k + 1))/2
ステップ 3: ステップ 2 を使用して、N = k + 1 のステートメントを証明しましょう。

証明するには: 1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
証明:

ステップ 2 で得られた結果の LHS と RHS の両方に (k+1) を加算します。
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

ここで、RHS 側から (k+1) 個の共通を取得します。
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

私たちが証明しようとしている声明によると:
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
したがって証明されました。

再帰の働き

上記の 3 つを要約することで、再帰的アプローチのステップを定義できます
手順:
● 基本ケース: 再帰関数には、
という終了条件が必要です。 プロセスはそれ自体の呼び出しを停止します。このようなケースは基本ケースとして知られています。基本ケースがないと、それ自体を呼び出し続けて、
に陥ってしまいます。 無限ループ。すぐに再帰の深さ*を超えてスローされます
エラーです。
● 再帰呼び出し: 再帰関数は、より小さいバージョンでそれ自体を呼び出します
主な問題の。このステップをそのまま書くときは注意が必要です
小さな問題が何なのかを正しく理解することが重要です。
● 小規模な計算: 通常、再帰ごとに計算ステップを実行します
電話。この計算ステップは、再帰呼び出しの前後でも実行できます
問題の性質によって異なります。

注: 再帰では、再帰呼び出しを保存する組み込みスタックが使用されます。したがって、
メモリのオーバーフローを避けるために、再帰呼び出しの数はできるだけ少なくする必要があります。もし
再帰呼び出しの数が最大許容量を超えています。
**再帰の深さ** を超えます。
ここで、Recursion

を使用していくつかの一般的な問題を解決する方法を見てみましょう。

問題文 - 数値の階乗を求める

アプローチ: PMI の 3 つのステップを理解し、それを次の方法で関連付けます
再帰

1. 帰納法ステップ: 数値 n - F(n) の階乗を計算する 帰納仮説: n-1 - F(n-1)
の階乗はすでに得られています。
2. F(n) を F(n-1) で表すと、F(n)=n*F(n-1) となります。したがって、
が得られます

public static int fat(int n){
int ans = ファクト(n-1); #仮定ステップ
ans * n を返します。 #仮定のステップから問題を解く
}

1. コードはまだ完成していません。欠品しているのはベースケースです。さあ、そうします 予行演習を行って、再帰を停止する必要があるケースを見つけます。 n = 5:
を考えてみましょう。

上でわかるように、n = 0、つまり 1 の答えはすでにわかっています。したがって、
これを基本ケースとして保持してください。したがって、コードは次のようになります:

public static int Factorial(int n){
if (n == 0) // 基本ケース
1 を返します;
それ以外
n*factorial(n-1) を返します。 // 再帰的なケース
}

以上が再帰 -1の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。