递归不仅是一种算法，也是一种思想，主要是对问题的简化，感觉还是比较重要的，所以这里独立出一篇进行介绍。
定义：
- 一种方法/函数调用自己的编程技术；
- 特征:
- 调用自身, 为了解决更小的问题；
- 存在某个足够简单的层次, 这一层次不需要调用自身就可以直接解答，并返回结果；
- 效率:
- 递归的调用，从调用处转移到方法的开始处，会有一定的额外开销，且中间变量和返回值也会占用系统内存；但使用递归常常是因为, 它从概念上简化了问题，而不是因为它更有效率；
- 程序设计中的递归, 类似于数学归纳法；
例子:
- 计算三角数字：三角数字指1,3,6,10,15,21..., 第n项的值 = 第n-1项的值 + n ; 或者说 第n项的值为从1到n的叠加，其算法实现如下：
private static int trangle(int n) {
//1. 循环实现
// int total = 0;
// while (n > 0) {
// total = total + n;
// --n;
// }
// return total;
//2. 递归实现
if (n == 1)
return 1;
else
return n + trangle(n - 1);
}
- 计算阶乘
private static int factorial(int n) {
if (n == 1)
return 1;
else
return n * factorial(n - 1);
}
- 计算n次幂(和上面差不多，就不写了)
- 递归的二分法查找，这个的完整实现在之前介绍数组的文章中已经给出了，所以下面只给出递归部分的代码了
public int find(long searchValue, int fromIndex, int toIndex) {
System.out.println("searchValue:" + searchValue + "_fromIndex:" + fromIndex + "_toIndex:" + toIndex);
int currentIndex = (fromIndex + toIndex) / 2;
if (array[currentIndex] == searchValue)
return currentIndex;
else if (fromIndex > toIndex)
return -1;
else if (array[currentIndex] < searchValue)
return find(searchValue, currentIndex + 1, toIndex);
else
return find(searchValue, fromIndex, currentIndex - 1);
}
- 汉诺(hanoi)塔问题
问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
private static void testHanoiTower() {
System.out.print("请输入要计算第几层：");
Scanner sc = new Scanner(System.in);
if (sc.hasNext()) {
String param = sc.next();
int n = Integer.parseInt(param);
hanoiTower(n, 'A', 'B', 'C');
System.out.println(n + "层汉诺塔需要移动" + count + "次");
}
}
private static int count = 0;
private static void hanoiTower(int n, char from, char inter, char to) {
//inter 中介塔
if (n == 1) {
System.out.println("hanoiTower >>>> n=" + n + ", from=" + from + ", to=" + to);
} else {
hanoiTower(n - 1, from, to, inter);
System.out.println("hanoiTower >>>> n=" + n + ", from=" + from + ", to=" + to);
hanoiTower(n - 1, inter, from, to);
}
count++;
}
分治算法 :
- 将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成
- 简而言之，把一个大问题分解为多个小问题，往复循环；
- 递归的二分法查找就是属于分治算法，方法中含有两个对自身的递归调用，但只有一个真的执行了
- 之前介绍的排序算法中有一种归并排序，也是对分治算法的一种非常典型的应用，想了解其实现的话可以参考那篇文章；
消除递归:
- 一个算法作为一个递归的方法通常从概念上很容易理解，但是，实际的运用中证明递归算法的效率不太高，这种情况下，把递归的算法转换成非递归的算法是非常有用的，这种转换经常会用到栈，所以实际中往往一开始就考虑基于栈的算法，而不是从递归的算法转化；
网友评论