概念

简单来说，当我们看到一个函数反复调用它自己的时候，递归就发生了。“递归”就意味着“反复”。

模版

1. 递归终止条件

2. 处理当前层逻辑

3. 下探到下一层（层数标记）

4. 清理当前层状态（可选）

思维要点

1. 不要人肉进行递归（最大误区）

2. 找到最近最简方法，将其拆解成可重复解决到问题（找最近重复子问题）

3. 数学归纳法思维

斐波那契数列(简单) (opens new window)

• 递归

var fib =function (n){
    if(n<2){
        return n
    }
    return fib(n-1)+fib(n-2)
}

//优化 
var fib =function (n,memory=[]){
    if(n<2){
        return n
    }
    if(!memory[n]){
        memory[n]=fib(n-1,memory)+fib(n-2,memory)
    }
    return memory[n]
}

• 动态规划解法

var = fib =function (n){
    if(n<=1){
        return n
    }
    let i =1
    let pre =0 
    let current =1
    let result =0
    while(i++ <n){
        result =pre +current
        pre = current
        current =result
    }
    return result
}

青蛙跳台阶(简单) (opens new window)

• 递归

var numWays = function(n) {
if (n <= 1) return 1;
  if (n === 2) return 2;
  return (numWays(n - 1) + numWays(n - 2)) % 1000000007;
};

• 计算备忘录时间

var numWays = function (n) {
  if (!n || n === 1) return 1;
  let a = 1; //临时保存n-2的值
  let b = 2; //临时保存n-1的值
  let result = n === 2 ? 2 : 0;
  for (let i = 3; i <= n; i++) {
    result = (a + b) % 1000000007;
    a = b;
    b = result;
  }
  return result;
};

扁平化嵌套列表迭代器(中等) (opens new window)

• DFS

嵌套的整型列表是一个树形结构，树上的叶子节点对应一个整数，非叶节点对应一个列表。

在这棵树上深度优先搜索的顺序就是迭代器遍历的顺序。

我们可以先遍历整个嵌套列表，将所有整数存入一个数组，然后遍历该数组从而实现 next 和 hasNext 方法

var NestedIterator = function(nestedList) {
    vals = [];
    const dfs = (nestedList) => {
        for (const nest of nestedList) {
            if (nest.isInteger()) {
                vals.push(nest.getInteger());
            } else {
                dfs(nest.getList());
            }
        }
    }
    dfs(nestedList);
};

NestedIterator.prototype.hasNext = function() {
    return vals.length > 0;
};

NestedIterator.prototype.next = function() {
    const val = vals[0];
    vals = vals.slice(1);
    return val;
};

字符串解码(中等) (opens new window)

n[string] 表示解析 [] 模板里面的内容，然后重复 n 次，即得到 n 个 string 拼接起来的字符串。

根据题意，[] 里面还可以再嵌套 [] ，例如 n[m[string]]。这种情况下，我们得先解析最内层的模板，重复 m 次，然后将 m * string 的结果作为外层模板的解析内容，再重复 n 次。

如果嵌套的层数更多，我们也是得先找到最内层的 []，就像洋葱一样，一层层剥开，然后再从内到外一层层解析和拼接。这种层层嵌套的描述很容易就让人想到了递归。

按照常规，写递归时不要过多考虑前后的递归函数，想好当前递归函数需要处理些什么就好了。

1. 在每个递归函数里我们处理一段没有嵌套模版的字符串。
2. 遇到英文字母时，进行简单的拼接。
3. 遇到数字时，累加数字。
4. 遇到 [ 时，说明接下来是一个嵌套模版，开始递归处理。递归处理嵌套模版结束后，我们回到了当前递归层级，需要的信息有两个：
5. 嵌套模版的解码字符串
6. 嵌套模版的结束坐标
7. 获得嵌套模版的解码字符串后，重复 n 次拼接到当前层级的解码字符串中，接着从嵌套模版的结束坐标开始继续处理当前层级的字符串。
8. 遇到 ] 时，说明处理当前层级模版的递归可以结束了，返回上一种情况需要的信息，解码字符串以及模版结束的坐标。

const decodeString =function (s,cur =0){
    let k = 0;
    let decoded=''
    while (cur< s.length){
        if(s[cur]==='['){
            const [str ,pos] =decodeString(s,cur+1);
            decoded += str.repeat(k);
            k=0;
            cur=pos;
        }else if(s[cur]===']'){
            return [decoded , cur +1]
        } else if (/[0-9]/.test(s[cur])) {
            k = k * 10 + parseInt(s[cur++]);
        } else {
            decoded +=s[cur++];
        }       
    }
    return decoded
}
//Time: O(N)O(N)，N 是解码后字符串的长度。
//Space: O(N)O(N)

• 循环+栈

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
    const reg = /[a-zA-Z]+|[0-9]+|\[|\]/g;
    const stack = [];
    const peek = () => stack[stack.length - 1]; // p.s. 这是一个不正经的栈

    while (reg.lastIndex < s.length) {
        let token = reg.exec(s)[0];
        if (token !== ']') {
            // 数字，字母，左括号通通入栈
            stack.push(token);
        } else {
            // 遇到右括号就开始出栈
            let str = '';
            // [] 中间的就是要重复的模式，把它们全部出栈，拼接起来
            while (peek() !== '[') {
                str = stack.pop() + str;
            }
            // 丢掉左括号
            stack.pop();
            // 左括号前面的一定是模式重复的次数
            const num = +stack.pop();
            // 把复制操作后的字符串放回栈中，作为外层 [] 模式的一部分
            stack.push(str.repeat(num));
        }
    }
    return stack.join('');
};
//Time: O(N)O(N)，N 是解码后字符串的长度。
//Space: O(N)O(N)