递归

递归四要素：

• 递归终止条件
• 当前层业务逻辑
• 进入下一层
• 清理当前层缓存

代码结构

// 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 
 
}

解决问题

斐波拉契数列

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

遍历树

爬楼梯

爬楼梯，可以一次1阶、2台阶，一共n台阶的楼梯有多少种爬法？