1. 再帰関数とは、平たく言えば、関数自体が自分自身を呼び出すことを意味します...
例: n!=n(n-1)!
関数 f(n)=nf(n-1) を定義します。
f(n-1) はこの定義の関数です。 。これが再帰です
2. 再帰を使用する理由: 再帰の目的は、プログラム設計を簡素化し、プログラムを読みやすくすることです。
3. 再帰の欠点: 非再帰関数は非常に効率的ですが、プログラミングが難しく、可読性が劣ります。再帰関数の欠点は、システムのオーバーヘッドが増加することです。つまり、再帰されるたびにスタック メモリがより多くのスペースを占有することになります。
4. 再帰の条件: タスクを完了するためのステートメントが存在し、再帰の要件が満たされている必要があります (分岐ではなく削減)。
5. 再帰的な進歩:
1. 再帰を使用して n の階乗を計算します。
分析: n!=n*(n-1)*(n-2)...*1
public int dReturn(int n){ if(n==1){ return 1; }else{ return n*dReturn(n-1);2. 再帰関数を使用して、1 から n までの累積を計算します: 1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1; }else{ return n+dReturn(n-1); 3. シーケンス 1、1、2、3、5、8、11... (各数値は前の 2 つの数値の合計であり、再帰関数が必要です) を出力する必要があります。
Java 再帰を使用して関数を表します: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
分析: X1=1; X3=X1+X2;
public int F(int n){ if(n==1){ return 1; }else if(n==2){ return 1; }else{ return F(n-1)+F(n-2); } }4.Javaは再帰的メソッドを使用して整数配列内の各要素を逆に出力します
public static void printAll(int index,int[] arr){ System.out.println(arr[index]); if(index > 0){ printAll(--index,arr) } } public static void main(String) [] args){ int[] arr={1,2,3,4,5};5. プログラミングソリューション: 未経産牛が生後 4 年目から毎年 1 頭の牛を出産すると、n 年目には何頭の牛が生まれるでしょうか?
public static int cattle(int n){ if(n<=0){ return 0; }else if(n<=3){ return 1; 戻り値 cattle(n-1)+cattle(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"年以降は合計 "+牛" になります);再帰、線形再帰、末尾再帰の概念は何ですか?
Java での再帰関数の呼び出し - 数値の階乗を求める
オーバーフローは考慮されません。通常、計算できるのは 69 の階乗のみです...
注: 0 の階乗は 0 です。 =1
1 より大きい任意の自然数 n の階乗表現:
n!=1×2×3×……×n
または、n!=n×(n-1)!
0 の階乗を検索すると、オンライン計算機が表示されます。これは非常に便利です。 ！
package test;import java.util.Scanner;public class DiGui {public static void main(String[] args) {// TODO 自動生成メソッド stubSystem.out.println("Enter an integer:");Scanner scan = new Scanner(System.in);int x = scan.nextInt();int result = digui(x);System.out.println(result);}//再帰関数 public static int digui(int x){if(x <=0){return 1;}else{return x*digui(x-1);}}}再帰: プロセスまたは関数には、その定義または説明内で直接または間接的にそれ自体を呼び出すメソッドがあり、通常、大規模で複雑な問題を、解決する元の問題に似た小さな問題に変換します。このケースは、再帰によって複雑な問題をより小さな問題に変換して解決できる方法を明確に示しています。以下は、再帰の原理を説明するための小さな例です。
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/public class Test { static int multiply( int n) { int 階乗; // ?? if ((n == 1) || (n == 0)) {階乗 = n; } else {階乗 = n * 乗算(n - 1); ; } public static void main(String[] args) { System.out.println(multiply(5));関数が呼び出されると、その変数用のスペースがランタイム スタック上に作成されます。以前に呼び出された関数の変数はスタック上に残りますが、新しい関数の変数によって隠されているため、アクセスできません。
プログラム内の関数には、パラメーター n とローカル変数階乗という 2 つの変数があります。次の図はスタックの状態を示しており、現在アクセス可能な変数が一番上にあります。他のすべての呼び出された変数は灰色で表示され、現在実行中の関数からアクセスできないことを示します。
値 5 を指定して再帰関数を呼び出すとします。スタックの内容は次のとおりです。スタックの最上位が最下位になります。
n multiply(n)階乗 5 multiply(5) 5*multiply(4) //最初の呼び出し 4 multiply(4) 4*multiply(3) //2 番目の呼び出し 3 multiply(3) 3*multiply(2 ) // 3 回目の呼び出し 2 multiply(2) 2*multiply(1) //4 回目の呼び出し 1 multiply(1) 1 //5 回目の呼び出し
上記の情報から、再帰によって問題を解決するためにどのように段階的に問題が最小化されるかが、メソッド呼び出しから開始して、メソッド呼び出しが終了するまで階乗結果がスタックにプッシュされ、最終的に結果が 1 つずつ返されることが簡単にわかります。スタックの一番上から。 1つずつ置換すると、結果は次のようになります。
n=1 1 は上向きに 1 を返します
n=2 2*multiply(1) は 2*1=2 を上向きに返します
n=3 3*multiply(2) は 3*(2*1)=6 を上向きに返します
n=4 4*multiply(3) は 4*(3*(2*1))=24 を上向きに返します
n=5 5*multiply(4) は上向きの値を返します 5*(4*(3*(2*1)))=120
注: multiply(1) または multiply(0) は値 1 を返すため、
したがって、2*multiply(1)=2*1=2 となります。
また、multiply(2) は再帰条件を満たしているため、再帰後に 2*multiply(1) に変換できます。
したがって、3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6 となります。
なぜなら、multiply(3) は再帰後に 3*multiply(2) に減らすことができるからです。
したがって、乗算(4)=4*乗算(3)=4*(3*乗算(2))=4*(3*(2*1))=24
類推すると、multiply(5)=5*multiply(4) となります。
これは、5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120 に減らすことができます。
バイトコード情報を見てみましょう。
public class Test extends java.lang.Object{ public Test(); コード: 0: aload_0 1: invokespecial #1; //メソッド java/lang/Object."<init>":()V 4: static int multiply を返す(int); コード: 0: iload_0 1: iconst_1 // int 型定数 1 をスタック 2 にプッシュします: if_icmpeq 9 // 2 つの int 型値を比較し、等しい場合は位置 9 にジャンプします。これは || です。 function 5: iload_0 //最初の条件が成立しない場合に実行され、ローカル変数 0 から int 型の値をロードします (n の値をスタックにプッシュします) 6: ifne 14 //0 に等しい場合、そうでない場合は比較します、位置 14 にジャンプします。 注: ここでのデフォルトの比較は 0 であるため、定数 0 をスタック 9 にプッシュする必要はありません。 iload_0 //ifne でジャンプがない場合は、ローカル変数 0 から int をロードします。 型の値(nの値をスタックにプッシュ) 10: istore_1 //int型の値をローカル変数1に格納(スタックの先頭から飛び出す値はローカル変数0でスタックにプッシュして格納した値) in ローカル変数 1) 11: goto 23 //位置 23 へ無条件ジャンプ 14: iload_0 //位置 6 での比較、0 に等しくない場合、この命令を実行し、ローカル変数 0 から int 型の値をロード (n の値をプッシュ) 15 : iload_0 //ローカル変数 0 から int 型の値をロード（n の値をスタックにプッシュ） 16: iconst_1 //int 型の定数 1 をスタックにプッシュ、定数 1 は n の 1 ですコード内の -1 17: isub / /減算演算を実行します、n-1 18: invokestatic #2; //メソッド multiply:(I)I、メソッド multiply を呼び出します 21: imul //乗算演算を実行します、n * multiply(n - 1) 22: istore_1 //ローカル変数1にint型の値を格納、factorial=... 23: iload_1 //ローカル変数1からint型の値をロード（factorialの結果をスタックにプッシュ） 24 : ireturn //メソッドは public static void main( java.lang.String[]); コード: 0: getstatic #3; // フィールド java/lang/System.out:Ljava/io/PrintStream; : invokestatic #2; //メソッド multiply:(I )I 7: invokevirtual #4; //メソッド java/io/PrintStream.println:(I)V 10: return }