再帰 -1-＆＃＆チュートリアル-php.cn

はじめに 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 に対して有効です

ステップを証明するには: 仮定ステップの結果から、次のことを証明します。 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 つを要約することで、再帰的アプローチのステップを定義できます

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

注: 再帰では、再帰呼び出しを保存する組み込みスタックが使用されます。したがって、メモリのオーバーフローを避けるために、再帰呼び出しの数はできるだけ少なくする必要があります。もし
再帰呼び出しの数が最大許容量を超えています。
**再帰の深さ
**を超えます。それでは、再帰を使用していくつかの一般的な問題を解決する方法を見てみましょう

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

アプローチ: PMI の 3 つのステップを理解し、同じものを使用して関連付けます

再帰

public static int fat(int n){

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