06--图解数据结构之递归小例子

张风捷特烈 · 简书 · · 2018-10-06 22:32

正文

零、前言--递归：

优点: 简洁+装B
代价：函数调用+系统栈空间
另外:使用递归，代码易不易读，这要因人而异，水平高的可能认为递归很易读，不递归反而罗里吧嗦的麻烦。
递归函数感觉就是自己调用自己,最后给自己一个台阶下
在此之前最好了解一下栈的机制：可参考：04-图解数据结构之栈--Stack

1.吃苹果


/**
 * 作者：张风捷特烈
 * 时间：2018/9/20 0020:16:45
 * 邮箱：[email protected]
 * 说明：一个简单的吃苹果递归
 */
public class AppleEaterClient {
    public static void main(String[] args) {
        Apple apple = new Apple(5);
        eat(apple);
        //苹果还剩4口
        //苹果还剩3口
        //苹果还剩2口
        //苹果还剩1口
        //苹果还剩0口
        //苹果吃完了
    }

    private static void eat(Apple apple) {
        if (apple.size <= 0) {
            System.out.println("苹果吃完了");
            return;
        }
        apple.size = apple.size - 1;
        System.out.println("苹果还剩" + apple.size + "口");
        eat(apple);

    }

    private static class Apple {
        public int size;
        public Apple(int size) {
            this.size = size;
        }
    }
}

2.拆分整数

/**
 * 作者：张风捷特烈
 * 时间：2018/10/6 0006:21:46
 * 邮箱：[email protected]
 * 说明：2306====>依次打印2 3 0 6
 */
public class PrintInt {
    public static void main(String[] args) {
        printInt(2306);
    }

    private static void printInt(int num) {
        if (num <= 0) {
            return;
        }
        printInt(num / 10);
        System.out.println(num % 10);
    }
}

递归1.png

3.递归求数组和

/**
 * 作者：张风捷特烈
 * 时间：2018/9/20 0020:16:56
 * 邮箱：[email protected]
 * 说明：递归求数组和
 */
public class Sum {
    public static int sum(int[] arr) {
        return sum(arr, 0);
    }

    /**
     * 递归函数
     * @param arr 数组
     * @param start 开始位置
     * @return 从开始位置到最后所有元素和
     */
    private static int sum(int[] arr,int start) {
        if (start == arr.length) {//终结点
            return 0;
        }

        return arr[start] + sum(arr, start + 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(new int[]{1, 2, 3, 4}));
    }
}