java编程基础(六)递归

2020-10-26   180 次阅读


递归

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

	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

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

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

a
a

2. 将一个圆盘从A移动到C:
a
a

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

a

a

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

代码

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);
    }
}

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

毕生所求无它,爱与自由而已