java代码实现递归

think in java 书中使用递归分析

代码如下：

public class Snake implements Cloneable {
    private Snake next;
    private char c;
    // Value of i == number of segments
    Snake(int i, char x) {
        c = x;
        if(--i > 0)
            next = new Snake(i, (char)(x + 1));
    }
    void increment() {
        c++;
        if(next != null)
            next.increment();
    }
    public String toString() {
        String s = ":" + c;
        if(next != null)
            s += next.toString();
        return s;
    }
    public Object clone() {
        Object o = null;
        try {
            o = super.clone();
        } catch (CloneNotSupportedException e) {}
        return o;
    }
    public static void main(String[] args) {
        Snake s = new Snake(5, 'a');
        System.out.println("s = " + s);
        Snake s2 = (Snake)s.clone();
        System.out.println("s2 = " + s2);
        s.increment();
        System.out.println(
                "after s.increment, s2 = " + s2);
    }
}

示意图如下：

snake.png

输出如下：

s = :a:b:c:d:e
s2 = :a:b:c:d:e
after s.increment, s2 = :a:c:d:e:f

分析：

• 在讲clone()的时候，为说明浅复制，举例此类;

一条 Snake（蛇）由数段构成，每一段的类型都是 Snake。所以，这是一个一段段链接起来的列表。
所有段都是以循环方式创建的，每做好一段，都会使第一个构建器参数的值递减，直至最终为零。
而为给每段赋予一个独一无二的标记，第二个参数（一个 Char ）的值在每次循环构建器调用时都会递增。
increment()方法的作用是循环递增每个标记，使我们能看到发生的变化；
而 toString 则循环打印出每个标记。

使用递归打印阶乘

@Test
public void test() {
    //10! = 10 * 9 * 8 * 。。。。1；
    System.out.println(get(36));
}
public static long get(int n) {
    long result = 1;
    if (n == 1) {
        result *= 1;
    }
    else {
        result = n * get(n-1);
    }
    return result;
}

使用递归打印斐波那契数列

    //第一和第二项是1，后面每一项是前二项之和，即1，1，2，3，5，8，13,...。
    //递归实现:
    public static int fun02(int n) {//n是第n个数，从 0 开始
        if (n > 1) {
            return (fun02(n-1) + fun02(n-2));
        }else {
            return 1;
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i <= 9; i++) {
            System.out.println(fun02(i));
        }
    }

使用递归打印 9 * 9乘法口诀表

public class multiplication99 {

    @Test
    public void test(){
        //getByFor(9);
        getByRecursion(9);
    }

    public static void getByFor(int n) {//for 循环实现
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.print(i+" * "+j+" = "+i*j+" ");
            }
            System.out.println();
        }
    }

    public static void getByRecursion(int n) {//递归 实现
        if (n == 1) {
            System.out.println("1 * 1 = 1 ");
        }
        else {
            getByRecursion(n-1);
            for (int j = 1; j <= n; j++) {
                System.out.print(n+" * "+j+" = "+n*j+" ");
            }
            System.out.println();
        }
    }
}