遞迴就是:方法自己呼叫方法的過程。
使用遞迴有兩個前提條件:
1.有一個趨近與終止的條件。
2.自己呼叫自己 。
如何實作遞迴?
最重要的方式是:實作遞歸,需要去推導出一個遞推公式。
思考遞歸的方式:橫向思考,根據遞推公式來思考。
程式碼的執行:是縱向執行。
先看下面程式碼:
public class TestDemo { public static void func(){ func(); //自己调用自己本身 } public static void main(String[] args) { func(); } }
上圖程式碼就是一個簡單的遞迴。
我們再來看這個程式碼的運行結果,
畫圖講解:
# 對於上圖這個遞歸來說,根本沒有一個趨於終止的條件,所以這個函數會無止盡的遞歸下去。每次遞迴都要在棧上開闢內存,一直在棧上開闢內存,總有一次會棧超出。
老鐵們要記住:一旦你寫的遞歸有問題,如果是邊界沒找對一定會報一個
public class TestDemo { public static void func(int n){ if(n == 1) return; func(n -1); } public static void main(String[] args) { func(3); } }
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)); } }
第一种写法: 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)); } }
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); } }
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)); } }
第一种方法:递归 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中文網其他相關文章!