1. 递归函数设计技巧

1.1 数学归纳法

带着这样的思维方式检查，可以大大减少程序错误率

基本思路：

  • step1: 验证P(1)成立
  • step2: 假设P(k)成立，证明P(k+1)也成立（证明前一项正确那么后一项也正确）
  • step3: 联合step1与step2，证明由P(1) -> P(n)成立

​

1.2 递归函数设计重要的三个部分

  1. 给『递归函数』一个明确的语义
  2. 实现边界条件时的程序逻辑
  3. 假设递归函数调用返回结果是正确的，实现本层函数逻辑

典型示例：

1
2
3
4
int f(int n){		//明确递归函数语义：f(n)用于求n的阶乘
    if( n == 1 ) return 1;	//实现边界条件
    return f(n - 1) * n;    //假设f(n-1)的实现是正确的，本层要实现阶乘就要用f(n-1)*n
}