递归
相信在数学中很常见这个概念, 实际在编程中也很常见这样的思维. 递归通俗的来说, 就是通过不断的将当前问题进行分解, 向前追溯直到终点然后再反推求解的过程.
通俗解读
案例一 : 看电影不知道在第几排
看电影时不清楚自己在第几排, 可以通过问前一排的人来得知, 进行加 1 即可. 那么用递归的思路求解代码就是这样的.
- function fn = (n) {
- if(n<= 0) return '座位不存在'
- if(n>1) {
- return fn(n-1)+1
- } else {
- return 1
- }
- }
案例二 : 走格子有多少走法
一共有 n 格, 每步可以走 1 格或者 2 格, 问一共有多少走法. 首先分解问题是第 n 格可以是前面 n-1 格走的, 也可能是 n-2 格走的. 所以 fn(n) = f(n-1) + f(n-2). 也要知道终止条件是只有 1 步, 那么只有一步的可能情况是还有 1 格, 也可能是还有 2 格.
- function fn = (n){
- if(n>2){
- return fn(n-1) + fn(n-2)
- } else if(n==2) {
- return 2
- } else {
- return 1
- }
- }
核心要点解析
可以分解为子问题
也就是返回的递归子问题与当前问题的逻辑拆解关系
这个问题与分解之后的子问题, 除了数据规模不同, 其他都是相同的
也就是子问题的解法与当前问题是完全一致的, 不需要区别写法
有终止条件
不再进行递归的判断条件, 并且知道临界条件的特殊值是可求的
实际问题
堆栈溢出
当递归层级过深的时候, 因为在递归的过程中会一直把临时变量封装为栈压入内存栈, 如果一直压入, 就会导致溢出导致服务崩溃. 通常的解决方案是设置一个递归深度来进行限制. 比如下面的代码: 则假定内存深度为 1000, 超过 1000 则抛出异常.
- let depth = 0
- let f = (n) => {
- ++depth
- if(depth>1000) throw error()
- if(n===1) return 1
- return fn(n-1) + 1
- }
说明: 这种不是很实用, 因为内存一般是动态变化的, 用定值没意义, 而如果动态获取内存, 又小题大做了.
重复计算
还是上面的递归计算走法的案例, 不难发现会重复计算一些中间步骤的走法, 导致浪费. 当然这种问题不一定会有, 和问题的分解有关.
优化方式是针对已经得到结果的走法计到 Map 缓存中直接使用.
- let f = ( n) => {
- if (n == 1) return 1;
- if (n == 2) return 2;
- // hasSolvedList 可以理解成一个 Map,key 是 n,value 是 f(n)
- if (hasSolvedList.containsKey(n)) {
- return hasSovledList.get(n);
- }
- ley ret = f(n-1) + f(n-2);
- hasSovledList.put(n, ret);
- return ret;
- }
无限递归
也就是没有办法找到终止条件的情况要考虑进, 主要是避免死循环或者脏数据的影响
来源: https://juejin.im/post/5bc60736f265da0aea69a848