数据结构与算法（第二章）

递归和回溯

什么是递归？

任何调用自身的函数就称为递归。

递归的特点

递归调用自身去解决一个规模比原始问题小一些的问题，递归通常简洁易懂。

每次递归调用都在内存中生成一个新的函数副本，函数结束，副本就从内存删除。

每个递归算法必须终止于一个基本情形。

经典递归算法用例

斐波那契数列、阶乘、归并排序、快速排序、图深度优先遍历、图广度优先遍历、汉诺塔、回溯算法等等。

递归实例

1、写一个算法，求解一个正整数n的阶乘的值。

private static int factorial(int n){
        if(n == 1){
            return n;
        }
        return n * factorial(n - 1);
    }

上面的算法严格来说并不正确，因为当n大于15时，就超出了int的范围，而这个时候程序返回必定不正确。那么只能扩大返回值的范围，这里我们用BigDecimal。

private static BigDecimal factorial(int n){
        if(n == 1){
            return BigDecimal.valueOf(n);
        }
        return BigDecimal.valueOf(n).multiply( factorial(n - 1));
    }

2、给定一个整形数组，用递归判断数组中的元素是否是有序（这里假设从小到大）的。

private static boolean isOrdered(int[] array,int index){
       //index为数组元素个数
       if(array.length == 1 || index == 1){
           return true;
       }
       return array[index - 1] <= array[index - 2] ? false:isOrdered(array,index - 1);
   } 

什么是回溯？

一种采用分治策略进行穷举搜索的方法。

有时求解一个问题最好的算法是尝试所有的可能性。

回溯算法经典实例

产生所有二进制串、背包问题、哈密顿回路、图着色算法。

回溯实例

生成长度为n的所有k进制串，串中每一位的取值是0~k-1。

public class Test {
    private static int[] array;

    public static void main(String[] args) {
        int n = 3, k = 2;
        array = new int[n];
        k_string(n, k);
    }
    private static void k_string(int n, int k) {
        if (n < 1) {
            for (int i : array) {
                System.out.print(i);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < k; i++) {
            //从数组末尾赋值(0~k-1)，直到填满
            array[n - 1] = i;
            k_string(n - 1, k);
        }
    }
}