算法-递归算法
1、定义：函数（方法）直接或间接调用自身。
- 必须要有一个明确的结束递归的条件
递归的退出条件：思考临界值-
拿到参数对它的范围进行判断
- 例子1:
- 例子2：
- 例子3：
2、递归的基本思想: 小规模→大规模；大规模→小规模
■ 求解过程：
- 由最小规模问题的解得出较大规模问题的解
- 由较大规模问题的解不断得出规模更大问题的解
- 最后得出原来问题的解
■ 拆解过程:
- 把规模大的问题变成规模较小的同类型问题
- 规模较小的问题又不断变成规模更小的问题
- 规模小到一定程度可以直接得出它的解
◼ 凡是可以利用上述思想【小规模→大规模；大规模→小规模】解决问题的，都可以尝试使用递归
很多链表、二叉树相关的问题都可以使用递归来解决，因为链表、二叉树本身就是递归的结构（链表中包含链表，二叉树中包含二叉树）
3、递归调用过程：
int sum(int n){if(n <= 1) return n;return n + sum(n -1);}
4、递归使用套路
① 明确函数的功能
- 先不要去思考里面代码怎么写，
首先搞清楚这个函数的干嘛用的，能完成什么功能？
② 明确原问题与子问题的关系
- 寻找 f(n) 与 f(n – 1) 的关系
③ 找出边界条件
思考问题规模小到什么程度可以直接得出解？
5、经典的递归算法
(1) 斐波那契数列
(2) 上楼梯（跳台阶）
(3) 汉诺塔
■ 斐波那契数列
斐波那契数列：1、1、2、3、5、8、13、21、34、……
int fib(int n){
if(n <= 2) return 1;return fib(n -1) + fib(n -2);
}
■ 上楼梯（跳台阶）
楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
假设 n 阶台阶有 f(n) 种走法，第 1 步有 2 种走法
如果上 1 阶，那就还剩 n – 1 阶，共 f(n – 1) 种走法
如果上 2 阶，那就还剩 n – 2 阶，共 f(n – 2) 种走法
所以 f(n) = f(n – 1) + f(n – 2)
int climbStairs(int n){
if(n <= 2) return 1;return climbStairs(n -1) + climbStairs(n -2);
}
■ 汉诺塔
其实分 2 种情况讨论即可
- 当 n == 1时，直接将盘子从 A 移动到 C
当 n > 1时，可以拆分成 3大步骤:
① 将 n – 1 个盘子从 A 移动到 B
② 将编号为 n 的盘子从 A 移动到 C
③ 将 n – 1 个盘子从 B 移动到 C
步骤 ① ③ 明显是个递归调用
// 将第i号盘子 从 from 移动到 to
void move(int i, String from, String to){System.out.println(i + "号盘子" + from + "->" + to);
}
/**
将n个盘子从柱子p1 经过柱子 p2 的协助 移动到 p3
*/
void hanoi(int n, String p1, String p2, String p3){if(n <= 1){
move(n, p1, p3);return;
}
hanoi(n-1, p1, p3, p2);//将n-1个盘子从柱子p1 经过柱子p3 的协助移动到了 p2
move(n, p1, p3);
hanoi(n-1, p2, p1, p3);//将n-1个盘子从柱子p2 经过柱子p1 的协助移动到了 p3
}
6、递归转非递归
递归100%可以转换成非递归
(1) 递归过程中的数据存储：
递归调用的过程中，会将每一次调用的参数、局部变量都保存在了对应的栈帧（Stack Frame）中
- 栈帧：调用方法所需要的内存空间(内存空间：存储数据，比如形参、局部变量)
(2) 递归转非递归
■ 自己构建一个栈
- 原理：模拟函数调用栈
■ 利用 重复迭代某个变量 替换掉栈帧中存储的变量
7、递归注意事项：
(1) 使用递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁
递归求出来的很有可能不是最优解，也有可能是最优解
(2) 使用尾递归可以对递归进行优化
如果本文对你有帮助的话记得给一乐点个赞哦，感谢！
墨蓝
我就是我
àì夳堔傛蜴生んèń
野性酷女
还没有评论，来说两句吧...