递归是什么
递归算法是计算机科学中非常重要的一个概念，用于解决很多的计算机科学问题。是一种直接或者间接调用自身函数或者方法的算法，大部分编程语言都支持函数的自调用。引用知乎使用者李继刚对递回的生动解释：
递归：你开启面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以开启它，你推开门，发现里面还有一扇门，你继续开启它。若干次之后，你开启面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙开启了几扇门。
递归的核心思想
递归的核心思想是分而治之，把问题分解成规模缩小的同类问题的子问题来求解的一种策略，我们通常都是从上而下的思维问题，而递归趋势从下往上进行思维，从小问题开始解决，最终解决大问题。
递归的三要素
1.明确递归终止条件
所谓递归其实就是有去有回，应该有一个明确的临界点，一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来。换句话说，该临界点就是一种简单情境，可以防止无限递归。
2.给出递归终止时的处理办法
刚刚说到，在递归的临界点存在一种简单情境，在这种简单情境下，应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。
3.提取重复的逻辑，缩小问题规模
递归的关键就是找到如何将大问题分解为小问题的规律。与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。A可以分解为若干子问题B、C、D情况，你可以假设子问题B、C、D已经解决，在此基础上思考如何解决问题A。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。从程式实现的角度而言，抽象出一个干净利落的重复的逻辑，来使用相同的方式解决子问题。
递归模型
public static long f(int n){
if(n == 1) //递归终止条件
return 1; // 简单场景
return n*f(n-1); // 相同重复逻辑，缩小问题规模
}
递归经典案例解析
1.斐波纳契数列
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、 ……
在数学上，斐波纳契数列以如下被以递回的方法定义：F0=0，F1=1，Fn=F(n-1) F(n-2)（n>=2， n∈N）。
经典解法：
public class FibonacciSequence {
/**
* @description 经典递归解法
*
* 斐波那契数列如下：
*
* 1,1,2,3,5,8,13,21,34,...
*
* *那么，計算fib(5)時，需要计算1次fib(4),2次fib(3),3次fib(2)，呼叫了2次fib(1)*，即：
*
* fib(5) = fib(4) fib(3)
*
* fib(4) = fib(3) fib(2) ；fib(3) = fib(2) fib(1)
*
* fib(3) = fib(2) fib(1)
*
* 这里面包含了许多次重复计算，而实际上只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
* 后面的optimizeFibonacci函式進行了优化，使时间复杂度降到了O(n).
*/
public static int fibonacci(int n) {
if (n == 1 || n == 2) { // 递归终止条件
return 1; // 简单场景
}
return fibonacci(n - 1) fibonacci(n - 2); // 相同重复逻辑，缩小问题规模
}
经典优化算法：
/**
* @description 對经典算法的优化
*
* 斐波那契数列如下：
*
* 1,1,2,3,5,8,13,21,34,...
*
* 那么，可以这样看：fib(1,1,5) = fib(1,2,4) = fib(2,3,3) = 5
*
* 也就是说，以1,1开头的斐波那契数列的第五项正是以1,2开头的斐波那契数列的第四项，
* 而以1,2开头的斐波那契数列的第四项也正是以2,3开头的斐波那契数列的第三项，
* 更直接地，我們就可以一步到位：fib(2,3,3) = 2 3 = 5,计算結束。
*
* 注意，前兩個引数是数列的开头兩项，第三个引数是想求的以前兩個引数开头的数列的第几項。
*
* 时间复杂度：O(n)
*
* @author rico
* @param first 数列的第一項
* @param second 数列的第二項
* @param n 目标项
* @return
*/
public static int optimizeFibonacci(int first, int second, int n) {
if (n > 0) {
if(n == 1){ // 递归终止条件
return first; // 简单场景
}else if(n == 2){ // 递归终止条件
return second; // 简单场景
}else if (n == 3) { // 递归终止条件
return first second; // 简单场景
}
return optimizeFibonacci(second, first second, n - 1); // 相同重复逻辑，缩小问题规模
}
return -1;
}
2.汉诺塔问题
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。
*有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，
*小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。
/**
* @description 在程式中，我們把最上面的盘子称为第一個盘子，把最下面的盘子称为第N個盘子
* @author rico
* @param level：盘子的個數
* @param from 盘子的初始地址
* @param inter 转移盘子時用於中转
* @param to 盘子的目的地址
*/
public static void moveDish(int level, char from, char inter, char to) {
if (level == 1) { // 递归终止条件
System.out.println("从" from " 移动盘子" level " 号到" to);
} else {
// 将evel-1個盘子從from移到inter(不是一次性移動，每次只能移动一個盘子,其中to用于周转)
moveDish(level - 1, from, to, inter); // 相同重复逻辑，缩小问题规模
// 将第level個盘子从A座移到C座
System.out.println("从" from " 移东盘子" level " 號到" to);
// 将level-1個盘子从inter移到to,from 用于周转
moveDish(level - 1, inter, from, to); // 相同重复逻辑，缩小问题规模
}
}
public static void main(String[] args) {
int nDisks = 30;
moveDish(nDisks, 'A', 'B', 'C');
}
网友评论