算法基础-递归

f(n)=f(n-1)+1 其中，f(1)=1    
int f(int n) {
  if (n == 1) return 1;
  return f(n-1) + 1;
}

递归的条件

• 一个问题的解可以分解为几个子问题的解

子问题就是数据规模更小的问题

• 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
• 存在递归终止条件

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环

如何编写递归代码

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
千万不要试图用人脑去分解递归的每个步骤

递归代码需要警惕堆栈溢出

递归代码都可以改为非递归