递归和回溯
什么是递归？
任何调用自身的函数就称为递归。
递归的特点
递归调用自身去解决一个规模比原始问题小一些的问题，递归通常简洁易懂。
每次递归调用都在内存中生成一个新的函数副本，函数结束，副本就从内存删除。
每个递归算法必须终止于一个基本情形。
经典递归算法用例
斐波那契数列、阶乘、归并排序、快速排序、图深度优先遍历、图广度优先遍历、汉诺塔、回溯算法等等。
递归实例
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);
}
}
}
