函数直接或间接调用自身
函数的调用过程
如果递归调用没有终止, 将会一直消耗栈空间, 最终导致栈溢出
所以必须有一个明确的结束递归条件, 也叫作边界条件, 递归基
递归不是为了得到最优解, 是为了简化解决问题的思路, 代码更加简洁
调用过程
基本思路
拆解问题
- 把大规模问题变成规模较小的同类型问题
- 规模小的问题, 继续变成更小的问题
- 规模小到一定程度可以直接得出它的解
求解
- 由小规模问题的解得出较大规模问题的解
- 较大规模问题的解不断得出规模更大问题的解
- 最后得出原来问题的解
链表, 二叉树相关问题都可以用递归来解决
套路
- 明确函数的功能, 搞清楚这个函数是干什么用的, 完成的功能
- 明确原问题与子问题的关系, 找到f(n) 和f(n - 1) 的关系
- 明确递归基, 边界条件, 问题规模小到什么程度可以直接得出解
例, 斐波那契
/**
* 使用递归实现
* @param n
* @return
*/
int fib0(int n) {
if (n <= 2) {
return 1;
}
int res1 = fib0(n - 1);
int res2 = fib0(n - 2);
return res1 + res2;
}
递推式T(n) = T(n - 1) + T(n - 2) + O(1), 时间复杂度O(2^n)
空间复杂度O(n)
递归调用的空间复杂度 = 递归深度 * 每次调用所需的辅助空间
递归调用过程中出现了很多的重复计算
优化1, 记忆化
用数组存放计算结果, 避免重复计算
/**
* 数组每个位置上, 放入计算的结果, 如果有值, 直接取值
* @param n
* @return
*/
int fib1(int n) {
if (n <= 2) return 1;
int[] array = new int[n + 1];
array[1] = array[2] = 1;
return fib1(n, array);
}
int fib1(int n, int[] array) {
if (array[n] == 0) {
array[n] = fib1(n - 1, array) + fib1(n - 2, array);
}
return array[n];
}
时间复杂度和空间复杂度都为O(n)
优化2
不适用递归调用, 直接使用数组
/**
* 自底向上计算值, 存在数组中
* @param n
* @return
*/
int fib2(int n) {
if (n <= 2) return 1;
int[] array = new int[n + 1];
array[1] = array[2] = 1;
for (int i = 3; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
时间和空间复杂度还是O(n)
优化3
每次运算只需要用到数组的两个元素, 所有可以使用滚动数组来优化
int fib3(int n) {
if (n <= 2) return 1;
int[] array = new int[2];
array[0] = array[1] = 1;
for (int i = 3; i <= n; i++) {
array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
}
return array[n % 2];
}
时间复杂度O(n), 空间复杂度O(1)
优化4
使用位运算取代模运算
int fib4(int n) {
if (n <= 2) return 1;
int[] array = new int[2];
array[0] = array[1] = 1;
for (int i = 3; i <= n; i++) {
array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
}
return array[n & 1];
}
优化5
使用两个变量来记录之前的结果
int fib5(int n) {
if (n <= 2) return 1;
int first = 1;
int second = 1;
for (int i = 3; i <= n; i++) {
second = first + second;
first = second - first;
}
return second;
}
优化6
使用线性代数解法, 特征方程
/**
* 特征方程
* @param n
* @return
*/
int fib6(int n) {
double c = Math.sqrt(5);
return (int)((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
}
例, 上楼梯
楼梯有n 阶, 上楼可以一步上1 阶, 也可以上2 阶, 走完n 阶共有多少种走法
- 假设n 阶台阶, 有f(n) 种走法, 第一步有2 中走法
- 如果上1 阶, 那就还剩n - 1, 共有f(n - 1) 种走法
- 如果上2 阶, 那就还剩n - 2 阶, 共有f(n - 2) 种走法
- 所以f(n) = f(n - 1) + f(n - 2)
public static void main(String[] args) {
ClimbStairs cl = new ClimbStairs();
System.out.println(cl.climbStairs(10));
}
int climbStairs(int n) {
if (n <= 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}
例, 汉诺塔
把A 的n 个盘子移动到C, 盘子编号为[1, n]
每次只能移动1 个盘子, 大盘子只能放在小盘子下面
思路:
2 种情况
- 当n == 1, 直接将盘子从A 移动到C
- 当n > 1, 分为3 个步骤
- 将n - 1 个盘子从A 移动到B
- 将编号为n 的盘子从A 移动到C
- 将n - 1 个盘子从B 移动到C
- 步骤1, 和3 为递归调用
public static void main(String[] args) {
new Hanoi().hanoi(3, "A", "B", "C");
}
void hanoi(int n, String p1, String p2, String p3) {
if (n == 1) {
move(n, p1, p3);
return;
}
hanoi(n - 1, p1, p3, p2);
move1(n, p1, p3);
hanoi(n - 1, p2, p1, p3);
}
void move(int no, String from, String to) {
System.out.println("(1)将" + no + "号盘子从" + from + "移动到" + to);
}
时间复杂度T(n) = 2 * T(n - 1) + O(1)
O(n^2)
空间复杂度 O(n)
尾调用
一个函数的最后一个动作为调用函数
如果最后一个动作是调用自身, 称为尾递归, 一些编译器对尾调用进行优化, 以达到节省栈空间的目的
尾调用优化, 也叫尾调用消除
如果当前栈帧上的局部变量等内容都不需要用了, 单签栈帧经过适当的改变后, 可以直接当做尾调用的函数的栈帧使用, 程序可以jump 到尾调用的函数代码
生成栈帧改变代码与jump 的过程称作尾调用消除, 或尾调用优化, 尾调用优化让位于尾位置的函数调用跟goto 语句性能一样高
阶乘
static int facttorial2(int n) {
if (n <= 1) return n;
return n * facttorial(n- 1);
}
// 尾调用优化
static int facttorial(int n) {
return facttorial(n, 1);
}
static int facttorial(int n, int result) {
if (n <= 1) return result;
return facttorial(n - 1, result * n);
}
斐波那契尾调用优化
static int fib(int n) {
if (n <= 2) return 1;
return fib(n, 1, 1);
}
static int fib(int n, int first, int second) {
if (n <= 1) return first;
return fib(n - 1, second,first + second);
}
