再帰とは、メソッドを単独で呼び出すプロセスです。
再帰を使用するには 2 つの前提条件があります:
1. アプローチ条件と終了条件があります。
2. 自分自身に電話してください。
再帰を実装するにはどうすればよいですか?
最も重要な方法は、再帰を実装するには、再帰式を導出する必要があるということです。
再帰についての考え方: 水平方向に考え、再帰公式に従って考えます。
コード実行: 垂直実行。
まず次のコードを見てください:
public class TestDemo { public static void func(){ func(); //自己调用自己本身 } public static void main(String[] args) { func(); } }
上記のコードは単純な再帰です。
このコードの実行結果を見てみましょう。
図の説明:
上の図の再帰の場合、終了する傾向のある A 条件がないため、この関数は無限に再帰的に実行されます。再帰するたびにスタックにメモリを割り当てる必要があるため、スタックにメモリを割り当て続けると、最終的にスタックがオーバーフローします。
ベテランの皆さん、覚えておいてください: 作成した再帰に問題が発生し、境界が正しく見つからない場合は、
が報告されます。このエラーが報告された場合、このエラーは終了条件が間違っているか、終了条件が書き込まれていないため、再帰の深さが大きすぎて、最終的にはスタック オーバーフローが発生する可能性があります。
上記のコードを正しくしたい場合は、終了条件を追加する必要があります。
正しいコードは次のとおりです:
public class TestDemo { public static void func(int n){ if(n == 1) return; func(n -1); } public static void main(String[] args) { func(3); } }
以下では、簡単な例を通じて再帰をより深く理解できます
例: n の階乗を求める再帰法 描画解析:
実装コード:
public class TestDemo { public static int fac(int n){ if(n == 1) { return 1; } int tmp = n * fac(n - 1); return tmp; } public static void main(String[] args) { System.out.println(fac(5)); } }
コード描画説明:
質問例: nの合計を求めます
図面解析:
実装コード:
第一种写法: public class TestDemo { public static int sumAdd(int n){ if(n == 1) { return 1; } int tmp = n + sumAdd(n - 1); return tmp; } public static void main(String[] args) { System.out.println(sumAdd(3)); } } 第二种写法: public class TestDemo { public static int sumAdd(int n){ if(n == 1) { return 1; } return n + sumAdd(n -1); } public static void main(String[] args) { System.out.println(sumAdd(3)); } }
質問例: 各項目を順番に出力する再帰実装 1 桁の数字
図面解析:
実装コード:
public class TestDemo { public static void print(int n){ if(n < 10){ System.out.print(n+" "); }else{ print(n/10); System.out.print(n%10+" "); } } public static void main(String[] args) { print(1234); } }
例:再帰メソッドを作成し、負でない整数を入力すると、それを構成する数値の合計が返されます。例: 1729 と入力すると、1 7 2 9が返されます。
実装コード:
public class TestDemo { public static int sumEveryone(int n){ if(n < 10){ return n; }else{ return n%10 + sumEveryone(n/10); } } public static void main(String[] args) { System.out.println(sumEveryone(7910)); } }
質問例: n 番目のフィボナッチ数を見つける
描画分析:
実装コード:
第一种方法:递归 public class TestDemo { public static int fib(int n){ if(n == 1 || n == 2){ return 1; }else{ return fib(n-2)+fib(n-1); } } public static void main(String[] args) { System.out.println(fib(5)); } 第二种方法:叫做循环(迭代)实现 public static int fib2(int n){ if(n == 1 || n==2){ return 1; } int f1 = 1; int f2 = 1; int f3 = 0; for (int i = 3; i < n; i++) { f3 = f1+f2; f1 = f2; f2 = f3; } return f3; } public static void main(String[] args) { System.out.println(fib2(45)); }
以上がJava 再帰: 概念と使用法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。