java编程基础（六）递归

刺骨的言语ヽ痛彻心扉 2022-12-01 12:00 281阅读 0赞

### 文章目录 ###

*  递归
 *  递归求阶乘
 *   *  逻辑分析
     *  代码
 *  递归解汉诺塔
 *   *  逻辑分析
     *  代码

# 递归 #

递归是指在方法中调用自身

void f() { 
    		f();
    	}

递归算法的运算逻辑，是将复杂问题一步步简化，简化成最简问题，然后再倒推求出结果，请看下面的例子：

# 递归求阶乘 #

## 逻辑分析 ##

求5的阶乘可以简化成求4的阶乘再乘5，依次类推，简化阶乘的最简问题：求0的阶乘，0的阶乘规定是1。再从0的阶乘倒推求出结果。

![a][]

## 代码 ##

package demo1;
    
    import java.math.BigInteger;
    import java.util.Scanner;
    
    /* 递归求阶乘 */
    public class Test1 { 
        public static void main(String[] args) { 
            while (true) { 
                System.out.print("求几的阶乘：");
                int n = new Scanner(System.in).nextInt();
                BigInteger r = f(BigInteger.valueOf(n));
                System.out.println("结果：\n"+r.toString());
            }
        }
    
        private static BigInteger f(BigInteger n) { 
            if (n.equals(BigInteger.ZERO)) { 
                return BigInteger.ONE;
            }
    
            return n.multiply(f(n.subtract(BigInteger.ONE)));
        }
    }

# 递归解汉诺塔 #

三根柱子，在一根柱子上从下往上按照大小顺序摞着圆盘。按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

## 逻辑分析 ##

将3层圆盘从A，用B辅助，移动到C，逻辑如下：

![a][a 1]

**移动3层圆盘可以简化为以下步骤：**

1.  先移动两层圆盘，从A，用C辅助，移动到B：

![a][a 2]  
![a][a 3]  
  
  
  
2. 将一个圆盘从A移动到C：  
![a][a 4]  
![a][a 5]

3. 再次移动两层圆盘，从B，用A辅助，移动到C：

![a][a 6]

![a][a 7]

以上，将三层汉诺塔，简化为移动两层汉诺塔，以此类推，可以简化成最简问题，移动一层汉诺塔。

## 代码 ##

package demo1;
    
    import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Test2 { 
        public static void main(String[] args) { 
            System.out.print("求几层汉诺塔：");
            int n = new Scanner(System.in).nextInt();
            f(n);
        }
    
        private static void f(int n) { 
            String z1="A",z2="B",z3="C";
            f(n,z1,z2,z3);
        }
    
        private static void f(int n, String z1, String z2, String z3) { 
            if (n == 1) { 
                System.out.println(z1+" -> "+z3);
                return;
            }
    
            f(n-1, z1,z3,z2);
    
            System.out.println(z1+" -> "+z3);
    
            f(n-1, z2,z1,z3);
        }
    }

[a]: /images/20221123/e262947aa2ec4fbc951f831837787508.png
[a 1]: /images/20221123/4601a3f9896449c8a44ccf8730176663.png
[a 2]: /images/20221123/d35e3a961673499d98296d6a7b784119.png
[a 3]: /images/20221123/18edd2dc6ade45129cdd1460b2addd6c.png
[a 4]: /images/20221123/3bdcfaafcf3d4e60b02971972e3412b7.png
[a 5]: /images/20221123/d8d2e1e26d9f4c758e19326c7c04081c.png
[a 6]: /images/20221123/7a7460f3c17246d5987726a1e997bf3b.png
[a 7]: /images/20221123/73bc39fe1ad54a539f3a3d2d6dffc214.png