Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).[1] The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Most computer programming languages support recursion by allowing a function to call itself within the program text. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code.

递归

递归就是函数自己调用自己。在一些函数式编程中没有循环，只能用递归的方式来编写函数。递归可以让程序更加的清晰，并没有性能上的优势。至于选择，引用Stack Overflow上的一句话“如果使用循环，程序性能可能更高；如果使用递归程序可能更容易理解。如何选择，要看什么对你来说更重要。”

基线条件与递归条件

编写递归函数时，一定要告诉它何时停止。每个递归函数都有两个部分，基线条件（base case）和递归条件（recursive case）。
基线条件就是何时不调用自己，递归条件是何时调用自己。

栈

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

调用栈

这个概念对理解递归很重要，这里便于理解不做专业的解释。调用栈是计算机内部使用的。调用一个函数的时候，该函数就进入调用栈，在栈顶添加了函数的内存块。调用另一个函数的时候，当前函数暂停并处于未完成状态。

递归调用栈

下面以阶乘factorial为例来展示一下递归调用栈。

代码：

1
2
3
4
5
def fact(x):
  if x == 1:
    return 1
  else:
    return x*fact(x-1)

图解：

尾递归

栈在递归中扮演了重要的角色，使用栈虽然方便，但要付出代价，每个函数调用都要占用一定内存，如果栈很高，会出现内存溢出。这时候有两种选择，使用循环或者尾递归。

尾递归就是用来减少这种堆栈的耗用，在这种递归代码在执行过程中是可以不需要回溯。一般是把当前的运算结果放在参数里传给下层函数。还是以阶乘为例：

1
2
3
4
5
6
7
8
9
def fact(x,a):
    if x < 0:
        return 0
    elif x == 0:
        return 1
    elif x == 1:
        return a
    else:
        return fact(x-1,x*a)

备注：上述尾递归就是用了一个参数a来维护递归的层次。同上过程中，最后不需要再依次回调这些函数，每次的结果a都存储了下来。

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著