算法与数据结构 - 递归 Recursion

定义

递归其实本质上类似于循环，只不过是调用本身循环体，来实现循环。

循环本身编译出来的汇编代码，和递归本身有异曲同工之处。

电影场景

盗梦空间

• 向下进入到不同到梦境当中；向上有回到原来一层。
• 通过声音同步会到上一层
• 每一层到环境和周围到人都是拷贝一份，主角等几个人穿越不同层级的梦境（发生和携带变化）

是不是和递归一样，第三点，主角可以穿越不同的梦境，同时把自己和携带的东西带到不同的梦境中，同时可以携带回来。就类似于函数里面的参数，同时还有一些全局变量。

简单的递归 实例

计算n!

n！ = 1 * 2 * 3 * 4* .... * n

function recursion(n) {

	if(n <= 1) return 1
    
    	return n * recursion(n);
}

递归最后的运行方式就称了一个递归栈，一层一层进入，然后拨开，类型于剥洋葱

递归的代码结构

• 递归终结条件（recursion terminator）
• 处理当前层的逻辑代码(process logic in current level)
• 下探到下一层（drill down）
• 清理当前层的状态（reverse the current level status if needed）

要点

1. 不用人肉进行递归，后面熟悉之后自己直接写代码。训练自己的递归思维，不要在手动去写递归树。
2. 找到最近最简方法，将其拆解称可重复解决的问题（重复子问题）。
3. 数学归纳法的思维。

实战

leetcode 70题 爬楼梯

首先我们简单的读一下题目

示例：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

找重复性！！！

找重复性！！！

找重复性！！！

抽象出问题的重复，刚开始可能比较难，我们可以画一个递归树，或者在纸上列出进行人肉

数学归纳法：

先想想n = 1的时候，n = 2， n = 3的时候

n = 1 ： 1

n = 2 : 1 + 1 ; 2

n = 3 : 1 + 1 + 1; 2 + 1; 1 + 2

n = 4 : ......

当然不要一直列下去，一般递归只需要列出前面几项，就可以开始找规律了。

f(3) = f(1) + f(2)

f(4) = f(2) + f(3)

......

所有的分项都是互斥的，而且 f(1) + f(2) 把 f(3)的所有可能性都已经包含进去了。

f(n) = f(n - 1) + f(n - 2)

show code

var climbStairs = function (n) {
   if (n === 1) return 1
   if (n === 2) return 2

   return climbStairs(n - 1) + climbStairs(n - 2)
};

当然这是种粗暴的递归方法，没有进行优化，有很多不必要的计算。

但并不能理解为递归不好。

递归本身并没有什么问题，问题是使用递归的方法，比如：是否把必要的结果做了缓存。

其本质也是循环只是碍于某些条件，没办法使用循环来解决问题。

leetcode 22题 括号生成

首先我们简单的读一下题目

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

思考，第一个字符要么放'(' ,要么放 ')' 先递归把所有的可能找出，再用if判断把不符合条件的项 filter

伪代码
/**
 * @param {number} n
 * @return {string[]}
 */
 const res = []
function generateParentthesis(n) { 
	_generate(n, '', res)
    return res;
}
function _generate(n, s, res) {
// 递归终结条件（recursion terminator）
	if n <= 0 
    		res.push(s)
        	return 
            
   // 处理当前层的逻辑代码(process logic in current level)
   
    let s1 = s + '('
    let s2 = s + ')'
    
    // 进入下一层
    	_generate(n - 1, s + '(', res)
        _generate(n - 1, s + ')'', res)
        
    // 清理当前层的状态
}

这时候就会发现，自己已经有了思路，大致的递归代码完成。

接下来需要做的就是优化代码。

• ( 和 ) 最多只有三个。
• 前面使用的( 要大于 ) ，不然不符合条件。左括号数量大于右括号

function generateParenthesis(n) {
  const res = []
  var _generate = function (left, right, n, s) {
  // terminator
    if (left >= n && right >= n) {
      res.push(s)
      return;
    }
    // logic & drill down
    if (left < n) _generate(left + 1, right, n, s + '(')
    if (right < left) _generate(left, right + 1, n, s + ')')
  }
  _generate(0, 0, n, '')
  return res;
}