快速理解递归

*数学归纳法理解

数学归纳法是:
1）验证 n=1时成立 
2）假设 n - 1 时成立，由此出发证明 n 时成立。

递归是:
1) 计算 base case( 相当于 n = 1） 
2) 假设我们已经计算出 n - 1 时的结果，如何由此出发计算 n 。这两者都是只关注base case，和 n-1、n间的过渡，而不关注每一步具体的运算。

• 斐波那契数列

能表示成递归的就是数学归纳法和菲博那契数列。
比如：f(n) = f (n - 1) + f(n - 2), f(1) = 0, f(2) = 1
变成如下形式：
def f(n):
  if n < 0:
    raise Exception()
  elif n == 1:
    return 0
  elif n == 2:
    return 1
  else:
    return f(n - 1) + f(n - 2)

• 其他理解

1. 写出递归函数也就是要处理好递归的3个主要的点:
   a)出口条件，即递归“什么时候结束”，这个通常在递归函数的开始就写好;
   b) 如何由"情况 n" 变化到"情况 n+1", 也就是非出口情况，也就是一般情况——"正在"递归中的情况；
   c) 初始条件，也就是这个递归调用以什么样的初始条件开始

2. 可以说，上述a,b,c三个条件组成了我们的递归函数；解决好上述3点，也就很容易地写出一个递归函数；剩下的就是去学习学习“数学归纳法”，请自己google之；不许要你称为归纳法专家，但只需要认证体会它的思路，对于你理解和创造递归函数有很大帮助