*数学归纳法理解
数学归纳法是:
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)
- 其他理解
写出递归函数也就是要处理好递归的3个主要的点:
a)出口条件，即递归“什么时候结束”，这个通常在递归函数的开始就写好;
b) 如何由"情况 n" 变化到"情况 n+1", 也就是非出口情况，也就是一般情况——"正在"递归中的情况；
c) 初始条件，也就是这个递归调用以什么样的初始条件开始可以说，上述a,b,c三个条件组成了我们的递归函数；解决好上述3点，也就很容易地写出一个递归函数；剩下的就是去学习学习“数学归纳法”，请自己google之；不许要你称为归纳法专家，但只需要认证体会它的思路，对于你理解和创造递归函数有很大帮助
