算法之递归案例

目录介绍

• 01.什么是递归
• 02.递归三个条件
• 03.斐波那契数列
• 04.找指定目录下所有文件
• 05.求1+2+…+N和
• 06.求100的阶乘
• 07.有序数组合并
• 08.求一个数乘方
• 09.背包问题
• 10.选择一支队伍
• 11.汉诺塔问题
• 12.二分法查找
• 13.警惕重复计算
• 14.开源项目推荐

01.什么是递归

• 递归：在一个方法内部对自身进行调用。利用递归可以用简单的程序来解决一些复杂的问题。比如：裴波那契数列的计算、汉诺塔、快排等问题。
• 递归结构包括两个部分：
  • 1、定义递归头。解答：什么时候不调用自身方法。如果没有头，将陷入死循环，也就是递归的结束条件。
  • 2、递归体。解答：什么时候需要调用自身方法。

02.递归三个条件

• 递归需要满足的三个条件。刚刚这个例子是非常典型的递归，那究竟什么样的问题可以用递归来解决呢？我总结了三个条件，只要同时满足以下三个条件，就可以用递归来解决。
• 1.一个问题的解可以分解为几个子问题的解
  • 何为子问题？子问题就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。
• 2.这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  • 比如电影院那个例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
• 3.存在递归终止条件+把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。
• 还是电影院的例子，第一排的人不需要再继续询问任何人，就知道自己在哪一排，也就是 f(1)=1，这就是递归的终止条件。

03.斐波那契数列

• 题目要求
  • 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
• 什么是斐波那契数列？
  • 1，1，2，3，5，8，13，21......斐波那契数列从第三项开始，每一项都等于前两项之和。斐波那契数列是由数学家 Leonardoda Fibonacci 以兔子繁殖为例子而提出的，所以也叫做“兔子数列”。
• 解题思路
  • 可以肯定的是这一题通过递归的方式是肯定能做出来，但是这样会有一个很大的问题，那就是递归大量的重复计算会导致内存溢出。另外可以使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来。下面我会把两个方法示例代码都给出来并给出两个方法的运行时间对比。
• 采用迭代法：int Fibonacci(int number) { if (number <= 0) { return 0; } if (number == 1 || number == 2) { return 1; } int first = 1, second = 1, third = 0; for (int i = 3; i <= number; i++) { third = first + second; first = second; second = third; } return third; }
• 采用递归：f(n) = f(n-1) + f(n-2)public int Fibonacci(int n) { if (n <= 0) { return 0; } if (n == 1||n==2) { return 1; } return Fibonacci(n - 2) + Fibonacci(n - 1); }
• 执行时间对比
  • 假设n为40我们分别使用迭代法和递归法计算，计算结果如下：
    • 1.迭代法：耗费时间1ms
    • 2.递归法：耗费时间272ms
• 为何递归效率低
  • 如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例
  • 从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。
  • 当时使用的是简单的用定义来求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2)，也就是说fib(n-2)调用了两次，同样的道理，调用f(n-2)时f(n-3)也调用了两次，而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。
• 递归迭代效率比较
  • 递归调用实际上是函数自己在调用自己，而函数的调用开销是很大的，系统要为每次函数调用分配存储空间，并将调用点压栈予以记录。而在函数调用结束后，还要释放空间，弹栈恢复断点。所以说，函数调用不仅浪费空间，还浪费时间。它的很多时间浪费在对函数调用的处理上。

04.找指定目录下所有文件

• 问题如下所示：
  • 列出（或删除）指定目录下的所有文件
• 实例代码，如下所示/** * 找出指定目录下的所有文件 * 递归 * * @param files * @return */ public static List<File> listFiles(File files) { List<File> fileList = new ArrayList<>(); if (files.isDirectory()) { for (File file : files.listFiles()) { fileList.addAll(listFiles(file)); } } else { fileList.add(files); } return fileList; }
• 测试代码public static void main(String args[]) { List<File> l = listFiles(new File("E:\\yc\\JavaProjectTest\\src")); System.out.println("共" + l.size() + "个文件"); for (File f : l) { System.out.println(f.getName()); //(这里只打印了文件的文件名) } }

05.求1+2+…+N和

• 题目要求
  • 问题如下所示：
    • 计算从1+2+3+…+N的和
  • 示例 :计算从1+2+3+…+100的和是5050
• 实例代码，如下所示/** * 获取从1+到N的和 * * @param num * @return */ public static int getSum(int num) { if (num == 1) { return 1; } return num + getSum(num - 1); }
• 测试代码public static void main(String args[]) { System.out.println(getSum(100)); }

//执行结果

5050

```

06.求100的阶乘

• 问题如下所示：
  • 求100的阶乘
• 实例代码，如下所示 public BigInteger sum(int i) { if (i == 1) { return BigInteger.ONE; } return BigInteger.valueOf(i).multiply(sum(i - 1)); }
• 测试代码public static void main(String[] args) { LoopMutiply test = new LoopMutiply(); try { System.out.println("yc计算结果：" + test.sum(50) + "!"); } catch (Exception e) { e.printStackTrace(); } }

07.有序数组合并

• 问题如下所示：
  • 给你两个有序数组，a是{ 1, 3, 4 }，b是{ 2, 3, 5, 6 }，请把他合成一个新的数组，然后输出……
• 实例代码，如下所示 // 合并数组 public static int[] mergeArray(int[] a, int[] b) { int result[] = new int[a.length + b.length]; if (checkSort(a) && checkSort(b)) { // 说明ab数组都是有序的数组 // 定义两个游标 int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) { result[k++] = a[i++]; } else { result[k++] = b[j++]; } } while (i < a.length) { // 说明a数组还有剩余 result[k++] = a[i++]; } while (j < b.length) { result[k++] = b[j++]; } } return result; } // 检查一个数组是否是有序1 2 3 public static boolean checkSort(int[] a) { boolean flag = false;// 默认不是有序的 for (int i = 0; i < a.length - 1; i++) { if (a[i] > a[i + 1]) { // 说明不是有序的 flag = false; break; } else { flag = true; } } return flag; }
• 测试结果public static void main(String[] args) { int[] a = { 1, 3, 4 }; int[] b = { 2, 3, 5, 6 }; int[] c = mergeArray(a, b); for (int n : c) { System.out.print(n + " "); } }

08.求一个数乘方

• 问题如下所示：
  • 求一个数的乘方
• 示例 :比如2^8,我们可以会求表达式2*2*2*2*2*2*2*2的值，但是如果y的值很大，这个会显得表达式很冗长。那么由没有更快一点方法呢？
• 问题分析
  • 一般稍微复杂一点的计算器上面都能求一个数的乘法，通常计算器上面的标志是 x^y 这样的按键，表示求 x 的 y 次方。一般情况下我们是如何求一个数的乘法的呢？
  • 数学公式如下是成立的：(Xa)b = Xa*b
  • 如果如果求28次方，我们可以先假定22=a,于是28 = （22）4 ，那么就是a4 ；假定 a2 = b，那么 a4 = b2，而b2可以写成(b2)1。于是现在28就转换成：b*b
  • 也就是说我们将乘方的运算转换为乘法的运算。求xy的值，当y是偶数的时候，最后能转换成两个数相乘，当时当y是奇数的时候，最后我们必须要在返回值后面额外的乘以一个x。
  • x^y= (x^2)^(y/2)，定义a=x^2,b=y/2, 则得到形如： x^y= a^b;
• 实例代码,如下所示public static int pow(int x,int y){ if(x == 0 || x == 1){ return x; } if(y > 1){ int b = y/2; int a = x*x; if(y%2 == 1){//y为奇数 return pow(a,b)*x; }else{//y为偶数 return pow(a,b); } }else if(y == 0){ return 1; }else{//y==1 return x; } }
• 测试结果public static void main(String[] args) { System.out.println("yc计算结果：" + pow(2,8) + "!"); }

09.背包问题

• 问题如下所示：
  • 背包问题也是计算机中的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中，以使得背包最后达到指定的总重量。
• 示例 :
  • 比如：假设想要让背包精确地承重20磅，并且有 5 个可以放入的数据项，它们的重量分别是 11 磅，8 磅，7 磅，6 磅，5 磅。这个问题可能对于人类来说很简单，我们大概就可以计算出 8 磅+ 7 磅 + 5 磅 = 20 磅。但是如果让计算机来解决这个问题，就需要给计算机设定详细的指令了。
• 问题分析
  • 一、如果在这个过程的任何时刻，选择的数据项的总和符合目标重量，那么工作便完成了。
  • 二、从选择的第一个数据项开始，剩余的数据项的加和必须符合背包的目标重量减去第一个数据项的重量，这是一个新的目标重量。
  • 三、逐个的试每种剩余数据项组合的可能性，但是注意不要去试所有的组合，因为只要数据项的和大于目标重量的时候，就停止添加数据。
  • 四、如果没有合适的组合，放弃第一个数据项，并且从第二个数据项开始再重复一遍整个过程。
  • 五、继续从第三个数据项开始，如此下去直到你已经试验了所有的组合，这时才知道有没有解决方案。
• 实例代码,如下所示public class Knapsack { private int[] weights; //可供选择的重量 private boolean[] selects; //记录是否被选择

    public Knapsack(int[] weights){

        this.weights = weights;

        selects = new boolean[weights.length];

    }

    /**

     * 找出符合承重重量的组合
     * @param total 总重量
     * @param index 可供选择的重量下标
     */
    public void knapsack(int total,int index){
        if(total < 0 || total > 0 && index >= weights.length){
            return;//没找到解决办法，直接返回
        }
        if(total == 0){//总重量为0，则找到解决办法了
            for(int i = 0 ; i < index ; i++){
                if(selects[i] == true){
                    System.out.println(weights[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        selects[index] = true;
        knapsack(total-weights[index], index+1);
        selects[index] = false;
        knapsack(total, index+1);
    }
}
```测试结果public static void main(String[] args) {
    int array[] = {11,9,7,6,5};
    int total = 20;
    Knapsack k = new Knapsack(array);
    k.knapsack(total, 0);
}

10.选择一支队伍

• 问题如下所示：
  • 在数学中，组合是对事物的一种选择，而不考虑他们的顺序。
• 示例 :
  • 比如有5个登山队员，名称为A,B,C,D和E。想要从这五个队员中选择三个队员去登峰，这时候如何列出所有的队员组合。（不考虑顺序）
• 问题分析
  • 还是以递归的思想来解决：首先这五个人的组合选择三个人分成两个部分，第一部分包含A队员，第二部分不包含A队员。假设把从 5 个人中选出 3 个人的组合简写为（5,3），规定 n 是这群人的大小，并且 k 是组队的大小。那么根据法则可以有：
  • (n,k) = (n-1,k-1) + (n-1,k)
  • 对于从 5 个人中选择 3 个人，
  • 有：(5,3) = (4,2)+(4,3)
  • (4,2)表示已经有A队员了，然后从剩下的4个队员中选择2个队员，(4,3)表示从5个人中剔除A队员，从剩下的4个队员中选择3个队员，这两种情况相加就是从5个队员中选择3个队员。
  • 现在已经把一个大问题转换为两个小问题了。从4个人的人群中做两次选择（一次选择2个，一次选择3个），而不是从5个人的人群中选择3个。
  • 从4个人的人群中选择2个人，又可以表示为：(4,2) = (3,1) + (3,2)，以此类推，很容易想到递归的思想。
• 实例代码,如下所示public class Combination { private char[] persons;//组中所有可供选择的人员 private boolean[] selects;//标记成员是否被选中，选中为true

    public Combination(char[] persons){

        this.persons = persons;

        selects = new boolean[persons.length];

    }

    public void showTeams(int teamNumber){

        combination(teamNumber,0);

    }

    /**

     *

     * @param teamNumber 需要选择的队员数
     * @param index 从第几个队员开始选择
     */
    public void combination(int teamNumber,int index){
        if(teamNumber == 0){//当teamNumber=0时，找到一组
            for(int i = 0 ; i < selects.length ; i++){
                if(selects[i] == true){
                    System.out.print(persons[i]+" ");
                }
            }
            System.out.println();
            return;
        }
        //index超过组中人员总数，表示未找到
        if(index >= persons.length ){
            return;
        }
        selects[index] = true;
        combination(teamNumber-1, index+1);
        selects[index] = false;
        combination(teamNumber, index+1);
    }
}
```测试结果public static void main(String[] args) {
    char[] persons = {'A','B','C','D','E'};
    Combination cb = new Combination(persons);
    cb.showTeams(3);
}

11.汉诺塔问题

• 问题如下所示：
  • 汉诺塔问题是由很多放置在三个塔座上的盘子组成的一个古老的难题。所有盘子的直径是不同的，并且盘子中央都有一个洞使得它们刚好可以放在塔座上。所有的盘子刚开始都放置在A 塔座上。这个难题的目标是将所有的盘子都从塔座A移动到塔座C上，每次只可以移动一个盘子，并且任何一个盘子都不可以放置在比自己小的盘子之上。
• 示例 :
  • 试想一下，如果只有两个盘子，盘子从小到大我们以数字命名（也可以想象为直径），两个盘子上面就是盘子1，下面是盘子2，那么我们只需要将盘子1先移动到B塔座上，然后将盘子2移动到C塔座，最后将盘子1移动到C塔座上。即完成2个盘子从A到C的移动。
  • 如果有三个盘子，那么我们将盘子1放到C塔座，盘子2放到B塔座，在将C塔座的盘子1放到B塔座上，然后将A塔座的盘子3放到C塔座上，然后将B塔座的盘子1放到A塔座，将B塔座的盘子2放到C塔座，最后将A塔座的盘子1放到C塔座上。
• 问题分析
  • 如果有四个，五个，N个盘子，那么我们应该怎么去做？这时候递归的思想就很好解决这样的问题了，当只有两个盘子的时候，我们只需要将B塔座作为中介，将盘子1先放到中介塔座B上，然后将盘子2放到目标塔座C上，最后将中介塔座B上的盘子放到目标塔座C上即可。
  • 所以无论有多少个盘子，我们都将其看做只有两个盘子。假设有 N 个盘子在塔座A上，我们将其看为两个盘子，其中(N-1)~1个盘子看成是一个盘子，最下面第N个盘子看成是一个盘子，那么解决办法为：
    • ①、先将A塔座的第(N-1)~1个盘子看成是一个盘子，放到中介塔座B上，然后将第N个盘子放到目标塔座C上。
    • ②、然后A塔座为空，看成是中介塔座，B塔座这时候有N-1个盘子，将第(N-2)~1个盘子看成是一个盘子，放到中介塔座A上，然后将B塔座的第(N-1)号盘子放到目标塔座C上。
    • ③、这时候A塔座上有(N-2)个盘子，B塔座为空，又将B塔座视为中介塔座，重复①，②步骤，直到所有盘子都放到目标塔座C上结束。
  • 简单来说，跟把大象放进冰箱的步骤一样，递归算法为：
    • ①、从初始塔座A上移动包含n-1个盘子到中介塔座B上。
    • ②、将初始塔座A上剩余的一个盘子（最大的一个盘子）放到目标塔座C上。
    • ③、将中介塔座B上n-1个盘子移动到目标塔座C上。
• 实例代码,如下所示/** * 汉诺塔问题 * @param dish 盘子个数(也表示名称) * @param from 初始塔座 * @param temp 中介塔座 * @param to 目标塔座 */ public static void move(int dish,String from,String temp,String to){ if(dish == 1){ System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to); }else{ move(dish-1,from,to,temp);//A为初始塔座，B为目标塔座，C为中介塔座 System.out.println("将盘子"+dish+"从塔座"+from+"移动到目标塔座"+to); move(dish-1,temp,from,to);//B为初始塔座，C为目标塔座，A为中介塔座 } }
• 测试结果move(3,"A","B","C");

12.二分法查找

• 问题如下所示：
  • 一个一系列数组，然后找到某个值的索引
• 问题分析
  • 一定是有序表,升序降序都可以
• 实例代码,如下所示/** * @param array 有序数组,但不限于数组 * @param start 开始查找的数组下标 * @param end 结束查找的数组下标 * @param searchValue 要搜索的值 * @return */ public static int search(int[] array, int start, int end, int searchValue){ if (array != null && array.length > 0){ int middle = (start + end) / 2; int middleValue = array[middle]; if (searchValue == middleValue){ return middle; }else if (searchValue < middleValue){ //查询值小于中值,在中值前面再次搜索,缩小范围 return search(array, start, middle-1, searchValue); }else { //查询值大于中值,在中值后面再次搜索,缩小范围 return search(array, middle+1, end, searchValue); } }else { return -1; } }
• 测试结果public static void main(String[] args) { int[] array = {1,3,5,7,9,12,14,15,19,20,22,23,28,30}; System.out.println(search(array, 0, array.length-1, 20)); }

13.警惕重复计算

• 除此之外，使用递归时还会出现重复计算的问题。刚才讲的第三个递归代码的例子，如果我们把整个递归过程分解一下的话，那就是这样的：
• 想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。
• 为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。
• 按照上面的思路，我们来改造一下刚才的代码：public int Fibonacci(int n) { if (n == 1) return 1; if (n == 2) return 2;

  // hasSolvedList 可以理解成一个 Map，key 是 n，value 是 f(n)

  if (hasSolvedList.containsKey(n)) {

    return hasSovledList.get(n);

  }

  int ret = f(n-1) + f(n-2);

  hasSovledList.put(n, ret);

  return ret;

}

```

• 除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题。在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。