什么是遞歸？用Java寫一個簡單的遞歸程序

遞歸的定義

遞歸（recursion）：以此類推是遞歸的基本思想，將規模大的問題轉化為規模小的問題來解決。

遞歸的要素

自定義遞歸函數，并確定函數的基本功能
例如Java從鍵盤輸入一個數，求輸入這個數的階乘。這個時候把輸入的數字作為形參

1. int diGuiTest(int n ){
2. }

找到遞歸函數循環結束條件
在求階乘的時候，我們不妨做出如下思考，例如輸入的n是5，那么5！是5 * 4 3 * 2 * 1，那是不是可以寫成
n f(n-1)?,程序運行過程如下：
5* f(4)
f(4)相當于重新調用了函數，形參為4
5 * 4* f(n-1)
f(3)相當于重新調用了函數，形參為3
5 * 4* 3* f(n-1)
f(2)相當于重新調用了函數，形參為2
5 * 4* 3 * 2* f(n-1)
f(1)相當于重新調用了函數，形參為1
很容易發現，這時候如果遞歸調用到n為1的時候，就要結束調用自身
代碼如下：

1. int diGuiTest(int n ){
2. if(n==1){
3. return 1;
4. }
5. else{
6. return n*f(n-1);
7. }
8. }

代碼示例

求1–100之間所有自然數的和

1. int sum (int n ){
2. if(n==1){
3. return 1 ;
4. }
5. else{
6. return n+sum(n-1);
7. }
8. }

斐波拉契數列
斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2) （n ≥ 2，n ∈ N*）

1. int fibonacci(int n ){
2.  
3. if (n<=1){
4. return n;
5. }
6. else {
7. return fibonacci(n-1)+fibonacci(n-2);
8. }
9.  
10. }

漢諾塔問題

首先我們考慮最簡單的情況：

將最上面的一塊放到B，再將最下面一塊放到C，再把最上面一塊從B放到C即可

1. public class Hanio {
2. public static void main(String[] args) {
3. char A='A';
4. char B='B';
5. char C='C';
6. hannio(3,A,B,C);
7. }
8. static void hannio(int paltfrom,char A,char B, char C){
9. if (paltfrom==1){
10. move (A,C);
11. }else {
12. hannio(paltfrom-1,A,C,B);//上面兩個盤子，通過C柱到B柱
13. move (A,C);
14. hannio(paltfrom-1,B,A,C);//
15. }
16. }
17. static void move(char A,char B){
18. System.out.println(A+"---->"+B);
19. }
20. }

到此這篇關于什么是遞歸?用Java寫一個簡單的遞歸程序的文章就介紹到這了,更多相關Java 遞歸內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

原文鏈接：https://blog.csdn.net/qq_44644993/article/details/113834046