算法：递归

递归指一个计算机程序调用其自身。递归有两个基本要素：

（1） 边界条件：确定递归到何时终止，也称为递归出口。

（2） 递归模式：大问题是如何分解为小问题的，也称为递归体。

递归函数只有具备了这两个要素，才能在有限次计算后得出结果。

比如下面的程序，是用于计算高斯求和公式:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

import sys

def Gauss(n):
    if n==1:
        return 1
    return Gauss(n-1) + n

print Gauss(int(sys.argv[1]))
           

$ python Gauss.py 300
45150
           

在程序中规定了f(1)的值，以及f(n)和f(n-1)的关系。这是数学归纳法思想的体现。想要得到f(n)，必须计算f(n-1)；想要f(n-1)，必须计算f(n-2)……直到f(1)。由于我们已经知道了f(1)的值，我们就可以填补前面所有的空缺，最终返回f(n)的值。

递归是数学归纳法在计算机中的程序实现。使用递归设计程序的时候，我们设置base case，并假设我们会获得n-1的结果，并实现n的结果。这就好像数学归纳法，我们只关注初始和衔接，而不需要关注具体的每一步。