递归（Recursion）

一、递归

递归：通过函数体来进行的循环

汇编：它没有所谓的循环嵌套这一说，你之前有一段指令写在什么地方，你不断的跳到之前的指令的地方去执行那条指令，这就是递归。

1. 从前有个山
2. 山里有个庙
3. 庙里有个和尚讲故事
4. 返回1

二、盗梦空间

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

计算 n!

n! = 1 * 2 * 3 * ... * n

def Factorial(n):
    if n <= 1 :
        return 1
    return n * Factorial(n - 1)

三、递归-代码模板

1. 终结条件（terminator）
2. 处理当前层逻辑（current level logic）
3. 下探到下一层（drill down）
4. 清理当前层（reverse）

C/C++模版：

void recursion(int level, int param) { 
  // recursion terminator
  if (level > MAX_LEVEL) { // 一、递归终结条件
    // process result 
    return ; 
  }

  // process current logic 
  process(level, param);  // 二、处理当前层逻辑

  // drill down 
  recursion(level + 1, param);// 三、下探到下一层

  // reverse the current level status if needed // 四、清理当前层
}

Java模版：

// Java
public void recur(int level, int param) { 
    // terminator 
    if (level > MAX_LEVEL) { 
        // process result 
        return; 
    }
    // process current logic 
    process(level, param); 
    // drill down 
    recur(level: level + 1, newParam); 
    // restore current status 
}  

Python模版：

def recursion(level, param1, param2, ...): 
    # recursion terminator 
    if level > MAX_LEVEL: 
   process_result 
   return 
    # process logic in current level 
    process(level, data...) 
    # drill down 
    self.recursion(level + 1, p1, ...) 
    # reverse the current level status if needed
    

JavaScript 模版：

const recursion = (level, params) =>{
   // recursion terminator
   if(level > MAX_LEVEL){
     process_result
     return 
   }
   // process current level
   process(level, params)
   //drill down
   recursion(level+1, params)
   //clean current level status if needed
   
}

四、思维要点

1. 不要人肉进行递归（最大误区） 刚开始学，可以把状态树画出来。到后面了直接看函数本身开始写即可。
2. 找到最近最简方法，将其拆解成可重复解决的问题（重复子问题）
3. 数学归纳法思维。