递归

使用Logo 编程语言创建的树，主要使用递归方法。每一个分支都可以看作是一棵树的缩小版。

在计算机科学中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。^[1]这种问题一般可以通过迭代来解决，但这需要在编程时识别和索引较小的问题实例。递归通过使用从自己的代码中调用自己的函数来解决这种 递归问题 recursive problem。这种方法可以应用于许多类型的问题，于是递归成为了计算机科学的核心思想之一。^[2]

递归的强大力量很明显来源于其有限描述所定义出的无限对象。通过类似的递归定义，有限的递归程序也可以用来描述无限的计算，即使程序中没有包含明显的重复。

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些 函数式编程语言 functional programming language(例如Clojure^[3])不定义任何循环结构，而只依赖递归来重复调用代码。在可计算性理论 computability theory中证明了这些递归语言是图灵完备 Turing complete 这意味着它们与基于while 和for等控制结构的命令式语言一样强大(可以用于解决相同的问题)。

从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的（因为尾递归调用可以沿用原函数的栈空间，不会新增栈帧，可以避免栈溢出——译者注）。

递归函数和算法

一种常用的计算机编程策略是将一个问题划分为与原问题相同类型的子问题，解决这些子问题，并将结果合并。这通常被称为 分治法 divede-and-conquer；在此基础上，加上一个存储子问题结果的查找表时（以避免重复解子问题而产生额外的计算时间），就产生了称为 动态规划dynamic programming 或 记忆化 memoization的方法。

递归函数的定义有一个或多个基本情况，函数对于输入参数只产生一个简单结果；以及一个或多个递归情况，表示程序对于输入参数进行递归(调用自身)。例如，阶乘函数可以通过等式 $0! = 1$ ，对于所有 $n > 0$ ， $n! = n (n - 1)!$ 来递归定义。这两个方程本身都不构成一个完整的定义，第一个方程是基本情况，第二个方程是递归情况。因为基本情况打破了递归的链条，所以有时也被称为 “终止情况”。

递归情况的工作可以看作是将复杂的输入分解为更简单的输入。在一个设计得当的递归函数中，每一次递归调用，都要简化输入问题，使得最终必然达到基本情况。(在正常情况下不打算终止的函数（例如，一些系统和服务器进程）是这方面的例外)。忽略编写基本情况，或不正确地测试，可能会导致 无限循环 infinite loop。

一些函数（例如计算级数 $e = 1/0! + 1/1! + 1/2! + 1/3! + ...$ ）的输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个参数（比如在上面级数例子中，可以是需要计算的项的数量）来提供一个 "停止标准"，以建立基本情况。这个例子用 共递归corecursion来处理其实会更自然，每次后续输出的项就是前面所有项的和；而这可以通过使用索引参数表示“计算第n项(第n部分的和)”来转换为递归。

递归数据类型

许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。 自引用self-referential定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。

归纳定义的数据

归纳定义是指定如何构造数据实例的定义。例如，字符串列表可以被归纳定义为（这里使用Haskell语法）：

data ListOfStrings = EmptyList | Cons String ListOfStrings

上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。

归纳定义的另一个例子是自然数 natural numbers（或正整数）：

一个自然数是1或 n + 1，其中 n 是一个自然数。

类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用 BNF： Backus–Naur form 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 (5 * ((3 * 6) + 8)) ，在一个表达式中有多个乘积或和运算。

协归纳定义的数据和共递归

协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。

用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：

字符串流是s这样的对象：
 头部head是字符串，且
 尾部tail是字符串流。

这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头head和尾tail以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。

共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 惰性编程语言 lazy programming language中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。

递归的类型

单重递归和多重递归

只包含单个自引用的递归称为 单重递归 single recursion，而包含多个自引用的递归称为 多重递归 multiple recursion。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括 树遍历tree traversal，如深度优先搜索。

单重递归的效率往往比多重递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多重递归则可能需要指数级的时间和空间，而且递归得更根本更彻底，在没有明确的堆栈的情况下，不能用迭代来代替。

多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。

下面是计算斐波那契数列第n项的python代码，分别使用多重递归和单重递归实现。

--Ricky：代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我

"""
Author: Ricky
Email: rickyzhu@foxmail.com
"""

def fib_MR(n):
    "Multiple Recursion computing the n-th Fibonacci term"
    assert n > 0 and isinstance(n, int), "n must be a positive integer"
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib_MR(n-1) + fib_MR(n-2) # 双重递归

def fib_SR(n):
    "Single Recursion computing the n-th Fibonacci term"
    assert n > 0 and isinstance(n, int), "n must be a positive integer"

    def _fib_SR(n):
        "reutnr the n-th and the (n-1)-th Fibonacci term"
        if n == 2:
            return 0, 1
        elif n == 3:
            return 1, 1
        else:
            An_1, An_2 = _fib_SR(n-1) # 单重递归
            return An_2 + An_1, An_1

    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return _fib_SR(n)[0]

print([fib_MR(i) for i in range(1,11)])

print([fib_SR(i) for i in range(1,11)])

间接递归

大多数递归的基本例子，以及这里介绍的大多数例子，都是直接递归，即一个函数调用自己。间接递归是指一个函数不是被它自己调用，而是被它调用的另一个函数（直接或间接）调用。例如，如果f调用f，那是直接递归，但如果f调用g，而g又调用f，那就是f的间接递归。三个或更多的函数链是可能的，例如，函数1调用函数2，函数2调用函数3，函数3再调用函数1。

间接递归也叫互递归 mutual recursion，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。

匿名递归

递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为 匿名递归 anonymous recursion。

下面是计算斐波那契数列第10项的javascript代码，通过匿名递归实现。

--Ricky：代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我

/*
 * @author: Ricky
 * @email: rickyzhu@foxmail.com
 */

(function (n) {
  if (n <= 2) {
    return n - 1;
  } else {
    return  arguments.callee(n - 1) + arguments.callee(n - 2); 
  }
})(10); // 计算斐波那契数列第10项

结构递归与生成递归

一些作者将递归分为 "结构性 "或 "生成性"。这种区别与递归程序从哪里获得它所处理的数据以及它如何处理这些数据有关：

消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。 ——————Felleisen, Findler, Flatt, and Krishnaurthi, How to Design Programs, 2001^[4]

因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某一部分的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。

生成递归是替代方法：许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：最大公约数、快速排序、二进制搜索、归并排序、牛顿法、分形和自适应集成。 ——————Matthias Felleisen, Advanced Functional Programming, 2002 ^[5]

这种区别在证明函数的终止性时很重要。

通过结构归纳，可以很容易地证明所有有限（归纳定义的）数据结构上的结构递归函数的终止：直观地看，每次递归调用都会接收较小的输入数据，直到达到一个基本情况。
相比之下，生成递归函数不一定会向其递归调用提供较小的输入，因此对其终止的证明不一定那么简单，避免无限递归需要更加谨慎。这些生成式递归函数通常可以解释为共递归函数——每一步都会产生新的数据，比如牛顿方法中的逐次逼近——而终止这种核心递归需要数据最终满足某个条件，而这个条件不一定能保证被满足。
就循环变体而言，结构性递归是指存在明显的循环变体，即大小或复杂度，它开始时是有限的，并在每个递归步骤中减少。
与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。

递归程序

递归过程

阶乘

递归过程的一个经典例子是用于计算自然数阶乘的函数:

[math]\displaystyle{ \operatorname{fact}(n) = \begin{cases} 1 & \mbox{if } n = 0 \\ n \cdot \operatorname{fact}(n-1) & \mbox{if } n \gt 0 \\ \end{cases} }[/math]

Pseudocode (recursive):

function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × … × 1]


    1. if n is 0, return 1
    2. otherwise, return [ n × factorial(n-1) ]


end factorial

伪代码 (递归):
函数阶乘是: 输入: 整数 n 且 n >= 0 输出: [n × (n-1) × (n-2) × … × 1] 1. 如果n 是0, 返回 1 2. 否则, 返回 [ n × 阶乘(n-1) ] 结束阶乘

The function can also be written as a recurrence relation:

该函数也可以写成递归关系式：

[math]\displaystyle{ b_n = nb_{n-1} }[/math]

[math]\displaystyle{ b_0 = 1 }[/math]

这种对递归关系的求值展示了在执行上述伪代码时将进行的计算。

计算n = 4的递归关系：
b₄ = 4 * b₃ = 4 * (3 * b₂) = 4 * (3 * (2 * b₁)) = 4 * (3 * (2 * (1 * b₀))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

这个阶乘函数也可以在不使用递归的情况下，通过使用典型的循环结构来描述，这些循环结构在命令式编程语言中可以找到：

Pseudocode (iterative):

function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × … × 1]


    1. create new variable called running_total with a value of 1


    2. begin loop
          1. if n is 0, exit loop
          2. set running_total to (running_total × n)
          3. decrement n
          4. repeat loop


    3. return running_total


end factorial

伪代码(递归):

函数 阶乘是:

输入: 整数 n ，使得 n >= 0

输出: [n × (n-1) × (n-2) × … × 1]


    1. 创建 一个名为 running_total 的新变量，其值为 1


    2. 开始 循环
          1. 如果 n 为 0, 则退出 循环
          2. 将 running_total 设置为 (running_total × n)
          3. 递减 n
          4. 重复 循环


    3. 返回 running_total


结束 阶乘

上面的命令式代码相当于这个使用累加器变量{{math|t}的数学定义:

[math]\displaystyle{ \begin{array}{rcl} \operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\ \operatorname{fact_{acc}}(n, t) & = & \begin{cases} t & \mbox{if } n = 0 \\ \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n \gt 0 \\ \end{cases} \end{array} }[/math]

上面的定义可以直接翻译成函数式编程语言，比如Scheme；这就是一个递归实现迭代的例子。

最大公约数

计算两个整数最大公除数的欧氏算法，可以递归写成。函数定义：

[math]\displaystyle{ \gcd(x,y) = \begin{cases} x & \mbox{if } y = 0 \\ \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y \gt 0 \\ \end{cases} }[/math]

Pseudocode (recursive):
function gcd is: input: integer x, integer y such that x > 0 and y >= 0 1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] end gcd

伪代码 (递归):
函数 gcd 是: 输入: 整数 x, 整数 y 使得 x > 0 且 y >= 0 1. 如果 y 为 0, 则返回 x 2. 否则, 返回 [ gcd( y, (x/y的余数) ) ] 结束 gcd

下面式最大公约数的递归关系，其中[math]\displaystyle{ x \% y }[/math]表示余下的 [math]\displaystyle{ x / y }[/math]：

[math]\displaystyle{ \gcd(x,y) = \gcd(y, x \% y) }[/math] if [math]\displaystyle{ y \neq 0 }[/math]

[math]\displaystyle{ \gcd(x,0) = x }[/math]

计算x = 27和y = 9的递归关系：
gcd(27, 9) = gcd(9, 27% 9) = gcd(9, 0) = 9
计算x = 111和y = 259的递归关系：
gcd(111, 259) = gcd(259, 111% 259) = gcd(259, 111) = gcd(111, 259% 111) = gcd(111, 37) = gcd(37, 111% 37) = gcd(37, 0) = 37

上面的递归程序是尾部递归；它相当于一个迭代算法，上面显示的计算显示了一个消除尾部调用的语言将执行的评估步骤。下面是使用显式迭代的相同算法的一个版本，适用于不消除尾部调用的语言。通过将其状态完全保持在变量x和y中，并使用循环结构，该程序避免了递归调用和增加调用栈。

Pseudocode (iterative):

function gcd is:

input: integer x, integer y such that x >= y and y >= 0


    1. create new variable called remainder


    2. begin loop
          1. if y is zero, exit loop
          2. set remainder to the remainder of x/y
          3. set x to y
          4. set y to remainder
          5. repeat loop


    3. return x


end gcd

伪代码(循环):

函数 gcd 是:

输入: 整数 x, 整数 y 使得 x >= y 且 y >= 0


    1. 创建 一个名为 余数的新变量


    2. 开始 循环
          1. 如果 y 为0, 则退出 循环
          2. 将 剩下部分设置为x / y 的余数
          3. 将x设置 为y
          4. 将y设置 为 余数
          5. 重复 循环


    3. 返回 x


结束 gcd

迭代算法需要一个临时变量，且即使给出了欧几里得算法的知识，但要通过简单的检查来理解其过程是比较困难的，虽然两种算法的步骤非常相似。

汉诺塔

汉诺塔 Towers of Hanoi 是一个数学难题，它的解法说明了递归的思想^[6]^[7]。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？

函数定义：

[math]\displaystyle{ \operatorname{hanoi}(n) = \begin{cases} 1 & \mbox{if } n = 1 \\ 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n \gt 1\\ \end{cases} }[/math]

汉诺塔的递归关系：

[math]\displaystyle{ h_n = 2h_{n-1}+1 }[/math]

[math]\displaystyle{ h_1 = 1 }[/math]

计算n = 4的递归关系：
hanoi(4) = 2hanoi(3) + 1 = 2(2hanoi(2) + 1) + 1 = 2(2(2hanoi(1) + 1) + 1) + 1 = 2(2(21 + 1) + 1) + 1 = 2(2(3) + 1) + 1 = 2(7) + 1 = 15

示例实现：

Pseudocode (recursive):
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

伪代码 (递归):
函数 hanoi 是: 输入: 整数 n, 使得n >= 1 1. 如果 n 为 1 则返回 1 2. 返回 [2 * [call hanoi(n-1)] + 1] 结束 hanoi

虽然不是所有的递归函数都有明确的解，但汉诺塔序列可以简化为一个明确的公式。^[8]

汉诺塔楼的明确公式：
h₁ = 1 = 2¹ - 1 h₂ = 3 = 2² - 1 h₃ = 7 = 2³ - 1 h₄ = 15 = 2⁴ - 1 h₅ = 31 = 2⁵ - 1 h₆ = 63 = 2⁶ - 1 h₇ = 127 = 2⁷ - 1 通常: h_n = 2ⁿ - 1, for all n >= 1

二分搜索

二分搜索 binary search算法是通过每次递归将数组切成两半来搜索有序数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。

在这个算法中使用了递归，因为算法每一轮都会把旧的数组切成两半，以创建一个新的数组。然后递归地调用二分搜索过程，这次是在新的（更小的）数组上。通常情况下，数组的大小是通过操作开始和结束索引来调整的。该算法表现对数级增长复杂度，因为它基本上是将问题域对半分。

C语言中二分搜索的实现实例:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array
  OUTPUT:
    result of binary_search



   以适当的初始条件调用二分搜索
  
  输入：
    data是按升序排列的整数数组，
    toFind是要搜索的整数
    count是数组中元素的总数
  输出：
   二分搜索的结果
 */

 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.
   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found

  二分搜索算法
    输入：
        data是按升序排列的整数数组，
        toFind是要搜索的整数，
        start是最小数组索引，
        end是最大数组索引
   输出：
        整数toFind在数组数据中的位置，
        如果未找到则为-1
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division

    //Stop condition.
    if (start > end)
       return -1;
    else if (data[mid] == toFind)        //Found?
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

递归数据结构（结构化递归）

递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。

"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."^[9]
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"^[10]

本节的例子说明了所谓的 "结构化递归"。这个术语的意思是递归程序作用于递归定义的数据。

只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。

链表

下面是一个链表节点结构的C语言定义。特别注意节点是如何通过自身来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。

struct node
{
  int data;           // some integer data  一些整数数据
  struct node *next;  // pointer to another struct node 指向另一个结构节点的指针
};

由于struct node数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的list_print过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在list_print过程中保持不变。

void list_print(struct node *list)
{
    if (list != NULL)               // base case  基本情况
    {
       printf ("%d ", list->data);  // print integer data followed by a space  打印数据和一个空格
       list_print (list->next);     // recursive call on the next node  递归调用下一个节点
    }
}

二叉树

下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。

struct node
{
  int data;            // some integer data  整数类型的数据
  struct node *left;   // pointer to the left subtree  指向左子树的指针
  struct node *right;  // point to the right subtree    指向右子树的指针
};

对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：

// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

对于上面定义的tree_contains的任何给定函数调用，最多会产生两次递归调用。

// Inorder traversal:
void tree_print(struct node *tree_node) {
        if (tree_node != NULL) {                  // base case
                tree_print(tree_node->left);      // go left
                printf("%d ", tree_node->data);   // print the integer followed by a space
                tree_print(tree_node->right);     // go right
        }
}

上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。

文件系统遍历

由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树遍历非常相似，因此树遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的前序遍历的示例。

import java.io.*;

public class FileSystem {

	public static void main (String [] args) {
		traverse ();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse () {
		File [] fs = File.listRoots ();
		for (int i = 0; i < fs.length; i++) {
			if (fs[i].isDirectory () && fs[i].canRead ()) {
				rtraverse (fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse (File fd) {
		File [] fss = fd.listFiles ();

		for (int i = 0; i < fss.length; i++) {
			System.out.println (fss[i]);
			if (fss[i].isDirectory () && fss[i].canRead ()) {
				rtraverse (fss[i]);
			}
		}
	}

}

这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。

实现问题

In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:

如果不是纯粹的递归函数(对基本情况进行单一检查，否则递归步骤)，而是实际的代码实现，则为了清晰或效率起见，可能会进行大量的修改。这些修改包括：

Wrapper function (at top)
Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)
Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough

包装器函数（在顶部）
短路到基本情况，也就是 远程递归 Arm's-length recursion（在底部）
混合算法（在底部）——一旦数据足够小，就切换到另一个的算法

On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.

在优雅简洁的基础上，包装器函数一般都会被接受，而对基本情况的短路则是被不被认可的的，尤其是在学术界。混合算法往往是为了提高效率，减少小规模问题下递归的开销，远程递归是一种特殊情况。

包装器函数

包装器函数 wrapper function是指被直接调用但本身不递归的函数，而是调用一个单独的辅助函数，由这个辅助函数实际上进行递归。

包装器函数可用于验证参数(这样递归函数就可以跳过这些参数)、执行初始化(分配内存、初始化变量)，特别是对于辅助变量，如“递归级别”或记忆的部分计算，以及处理异常和错误。在支持嵌套函数的语言中，辅助函数可以嵌套在包装器函数内部，并使用共享的作用域。在没有嵌套函数的情况下，辅助函数是一个独立的函数，如果可能的话，辅助函数会被定义为私有的(因为它们没有被直接调用) ，通过使用引用传递的方式与包装器函数共享信息。

基本情况下的短路

基本情况下的短路，也称为远程递归（arm's-length recursion），包括在进行递归调用之前检查基本情况——即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要再单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是0！=1，而对于1！立即返回1时短路，可能会漏掉0；这个问题可以通过包装器函数来缓解。

短路主要是在遇到很多基本情况的时候考虑使用，比如树的空指针，它随着函数调用次数呈线性增长，因此对于 $O (n)$ 算法来说，可以大大节省成本。以深度优先搜索为例，树的短路对应于将叶子节点（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)级别的时间。

从概念上讲，短路递归可以认为和标准递归具有相同的基本情况和递归步骤，只是对基本情况的剪岔放在了递归前；也可以认为是具有不同的基本情况（比标准基本情况去掉一步）和更复杂的递归步骤，即 "先检查，若有效再递归"，如在树中考虑叶子节点而不是空节点作为基本情况。由于短路的流程比较复杂，相比标准递归中基本情况和递归步骤的清晰分离，短路往往被认为是糟糕的风格，尤其是在学术界。^[11]

深度优先搜索

在二叉树的 深度优先搜索 depth-first search（DFS）中给出了一个短路的基本例子。

DFS的标准递归算法是：

基本情况：如果当前节点为Null，返回false。
递归步骤：否则，检查当前节点的值，如果匹配则返回true，否则对子节点进行递归。

在短路的情况下，这反而是：

检查当前节点的值，如果匹配则返回true，
否则，在子代上，如果不是Null，则递归。

就标准步骤而言，这将基本情况的检查移到了递归步骤之前。或者，这些可以分别被认为是基例和递归步骤的不同形式。注意，这需要一个封装函数来处理树本身为空的情况（根节点为Null）。

对于高度为h的完美全二叉树，有2^h+1−1个节点和 2^h+1个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。

在C语言中，标准的递归算法可以实现为：

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case  基本情况
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

短路算法可以实现为：

// Wrapper function to handle empty tree  处理树为空的包装器函数
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree  空树
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function  调用辅助函数
}

// Assumes tree_node != NULL  假设树不为空
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found  找到节点
    else  // recurse 递归
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

请注意布尔运算符&& (AND)在短路计算的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔表达式，所以整个表达式也是一个布尔表达式。这是递归短路中常见用法。布尔运算符||（OR）在短路计算时，只有在左子树的运算返回false时，才会执行右子树的运算。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，而对效率却没有任何好处。

混合算法

由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如平铺合并排序 tiled merge sort。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。

递归 VS 迭代

递归和迭代的表达能力是一样的：递归可以用显式调用栈的迭代代替，而迭代可以用尾递归代替。哪种方法更合适，取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选，特别是对于简单递归，因为它避免了函数调用的开销和调用栈管理，但在多重递归问题时通常还是要用到递归方法。相比之下，在函数式语言中，递归是首选的，因为尾递归优化只带来很少的开销。使用迭代实现算法可能不容易实现。

比较x_base中，由x_n = f(n, x_n-1)定义的计算x_n的模板:

function recursive(n)
    if n == base
        return x_base
    else
        return f(n, recursive(n-1))

function iterative(n)
    x = x_base
    for i = base+1 to n
        x = f(i, x)
    return x

对于命令式语言，开销是定义函数，对于函数式语言，开销是定义累加器变量x。

例如，在C语言中，一个阶乘函数可以通过分配给循环索引变量和累加器变量来迭代实现，而不是通过递归传递参数和返回值。

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

表达能力

今天使用的大多数编程语言都允许直接编写递归函数和程序。当这样的函数被调用时，程序的运行时环境会跟踪该函数的各种实例（通常使用调用栈，也可能会使用其他方法）。每一个递归函数都可以被转换成迭代函数，用迭代控制构造代替递归调用，并用程序显式管理的自己的栈来模拟系统调用栈。^[12]^[13]

相应得，所有可以被计算机求解的迭代函数和程序(见图灵完备性)都可以用递归函数来表达；在函数式语言中，诸如while循环和for循环等迭代控制构造经常以递归形式重写^[14]^[15]。然而，在实践中，这种重写依赖于尾部调用的消除，而这并不是所有语言的特征。C、Java和Python是值得注意的主流语言，在这些语言中，所有的函数调用（包括尾部调用）都可能会引起栈分配，而使用循环结构则不会出现这种情况；在这些语言中，以递归形式重写的迭代程序可能会造成调用栈溢出，不过尾部调用消除可能是语言规范中没有涉及的功能，同一语言的不同实现在尾部调用消除能力上可能会有所不同。

性能问题

在偏重于迭代循环结构的语言（如C语言和Java）中，由于管理栈所需的开销，以及函数调用的相对缓慢，递归程序通常会有显著的时间和空间成本；在函数式语言中，函数调用（尤其是尾部调用）通常是一个非常快的操作，这种差异通常不太明显。

作为一个具体的例子，上述 "阶乘"例子的递归和迭代实现之间的性能差异很大程度上取决于所使用的编译器。在偏好循环结构的语言中，迭代版本可能比递归版本快几个数量级。在函数式语言中，两种实现的总体时间差异可能可以忽略不计；事实上，先乘大数而不是先乘小数的成本（这里给出的迭代版本就是这么做的）可能会超过选择迭代所节省得任何时间。

栈空间

在一些编程语言中，调用栈的最大规模远小于堆中的可用空间，而递归算法往往比迭代算法需要更多的栈空间。因此，这些语言有时会对递归的深度进行限制，以避免栈溢出；Python就是这样一种语言^[16]。注意下面关于尾部递归的特殊情况的注意事项。

漏洞

由于递归算法可能会引发栈溢出，因此它们可能容易受到异常或恶意输入的影响^[17]。一些恶意软件专门针对程序的调用栈，并利用栈固有的递归特性^[18] 。即使在没有恶意软件的情况下，由无约束递归引起的栈溢出也会对程序造成致命的影响，而异常处理逻辑可能无法阻止相应进程被终止^[19]。

多重递归问题

多重递归问题本质上是递归的，因为它们需要跟踪之前的状态。一个例子是深度优先搜索中的树遍历。虽然可以同时使用了递归和迭代方法^[20]，但它们与单重递归的列表遍历和列表中的线性搜索相比，后者是一种自然的迭代方法。其他例子包括分治算法(如快速排序)和函数(如Ackermann函数)。所有这些算法都可以在显式栈的帮助下迭代地实现，但是程序员在管理栈方面所付出的努力，以及结果程序的复杂性，无疑超过了迭代解决方案的任何优势。

重构递归

递归算法可以用非递归的对应算法来替换^[21]。替换递归算法的一种方法是用堆内存代替栈内存来模拟它们^[22] 。另一种方法是完全基于非递归方法来开发替换算法，这可能是一个挑战^[23] 。例如，用于通配符匹配的递归算法，如Rich Salz的wildmat算法^[24]，曾经是典型的算法。为了避免递归的缺点^[25]，人们开发了用于相同目的的非递归算法，如Krauss通配符匹配算法，并在收集测试和性能分析等技术的基础上逐步改进。^[26]

尾递归函数

尾递归函数是指所有递归调用都是尾调用，因此没有任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，阶乘函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它存在递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。

Tail recursion:

Augmenting recursion:

//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}

//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return fact(n - 1) * n;
}

尾递归的意义在于，当进行尾递归调用（或任何尾调用）时，调用者的返回位置不需要保存在调用栈上，当递归调用返回时，它将直接在先前保存的返回位置上进行分支。因此，在识别尾调用这一特性的语言中，尾部递归既节省了空间又节省了时间。

执行顺序

在一个函数只调用自己一次的简单情况下，放置在递归调用之前的指令在每次递归都会被执行一次，且比放置在递归调用之后任何指令更早执行。后者在达到最大递归后会才被重复执行。考虑这个例子：

函数1

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

函数 2 两行代码对调

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

递归算法的时间效率

递归算法的 时间效率 time efficiency 可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。

捷径规则（主定理）

如果函数的时间复杂度为以下形式：

[math]\displaystyle{ T(n) = a \cdot T(n / b) + f(n) }[/math]

那么时间复杂度的大O为：

如果[math]\displaystyle{ f(n) = O(n ^ { \log_b a - \epsilon}) }[/math]，对于一些常数[math]\displaystyle{ \epsilon \gt 0 }[/math]，那么 [math]\displaystyle{ T(n) = \Theta(n ^ {\log_b a}) }[/math]
如果 [math]\displaystyle{ f(n) = \Theta(n ^ { \log_b a }) }[/math], 那么 [math]\displaystyle{ T(n) = \Theta(n ^ { \log_b a} \log n) }[/math]
如果 [math]\displaystyle{ f(n) = \Omega(n ^ { \log_b a + \epsilon}) }[/math] 对于一些常数 [math]\displaystyle{ \epsilon \gt 0 }[/math], 且如果[math]\displaystyle{ a \cdot f(n / b) \leq c \cdot f(n) }[/math] 对于一些常数 $c$ < 1 和所有足够大的 $n$ , 则 [math]\displaystyle{ T(n) = \Theta(f(n)) }[/math]

其中， $a$ 代表每一级递归的递归调用次数， $b$ 代表下一级递归的输入会小多少（即把问题分成多少块）， $f (n)$ 代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。

另请参阅

函数式编程 Functional programming
SQL中的层次化和递归查询 Hierarchical and recursive queries in SQL
Kleene–Rosser悖论 Kleene–Rosser paradox
开放式递归 Open recursion
递归 Recursion
西尔平斯基曲线 Sierpiński curve
麦卡锡 91函数 McCarthy 91 function
μ-递归函数 μ-recursive functions
原始递归函数 Primitive recursive functions
Tak（函数）Tak (function)

参考文献

↑ "1: Recurrent Problems". Concrete Mathematics. 1990. ISBN 0-201-55802-5. http://www-cs-faculty.stanford.edu/~knuth/gkp.html.
↑ Discrete Mathematics with Applications (2nd ed.). 1995. p. 427. ISBN 978-0-53494446-9. https://archive.org/details/discretemathema000epps/page/427.
↑ "Functional Programming | Clojure for the Brave and True". www.braveclojure.com. Retrieved 2020-10-21.
↑ harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= art V "Generative Recursion
↑ Felleisen, Matthias (2002). "Developing Interactive Web Programs". In Jeuring, Johan. Advanced Functional Programming: 4th International School. Springer. p. 108. ISBN 9783540448334. https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108.
↑ Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi
↑ Epp 1995, pp. 427–430: The Tower of Hanoi
↑ Epp 1995, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence
↑ Wirth 1976, p. 127
↑ Wirth 1976, p. 127
↑ Mongan, John; Giguère, Eric; Kindler, Noah (2013). Programming Interviews Exposed: Secrets to Landing Your Next Job (3rd ed.). Wiley. p. 115. ISBN 978-1-118-26136-1. https://archive.org/details/programminginter00mong_658.
↑ Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384.
↑ Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017.
↑ Shivers, Olin. "The Anatomy of a Loop - A story of scope and control" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.
↑ Lambda the Ultimate. "The Anatomy of a Loop". Lambda the Ultimate. Retrieved 2012-09-03.
↑ "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation". Docs.python.org. Retrieved 2012-09-03.
↑ Krauss, Kirk J. (2014). "Matching Wildcards: An Empirical Way to Tame an Algorithm". Dr. Dobb's Journal.
↑ Mueller, Oliver (2012). "Anatomy of a Stack Smashing Attack and How GCC Prevents It". Dr. Dobb's Journal.
↑ "StackOverflowException Class". .NET Framework Class Library. Microsoft Developer Network. 2018.
↑ "Depth First Search (DFS): Iterative and Recursive Implementation". Techie Delight. 2018.
↑ Mitrovic, Ivan. "Replace Recursion with Iteration". ThoughtWorks.
↑ La, Woong Gyu (2015). "How to replace recursive functions using stack and while-loop to avoid the stack-overflow". CodeProject.
↑ Moertel, Tom (2013). "Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick".
↑ Salz, Rich (1991). "wildmat.c". GitHub.
↑ Krauss, Kirk J. (2008). "Matching Wildcards: An Algorithm". Dr. Dobb's Journal.
↑ Krauss, Kirk J. (2018). "Matching Wildcards: An Improved Algorithm for Big Data". Develop for Performance.

此词条由Solitude初步翻译。

本词条由Ricky审校。

[1] "1: Recurrent Problems". Concrete Mathematics. 1990. ISBN 0-201-55802-5. http://www-cs-faculty.stanford.edu/~knuth/gkp.html.

[2] Discrete Mathematics with Applications (2nd ed.). 1995. p. 427. ISBN 978-0-53494446-9. https://archive.org/details/discretemathema000epps/page/427.

[3] "Functional Programming | Clojure for the Brave and True". www.braveclojure.com. Retrieved 2020-10-21.

[Felleisen_HtDP_2001-4] rvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= art V "Generative Recursion

[Felleisen_2002_108-5] Felleisen, Matthias (2002). "Developing Interactive Web Programs". In Jeuring, Johan. Advanced Functional Programming: 4th International School. Springer. p. 108. ISBN 9783540448334. https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108.

[6] Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi

[7] Epp 1995, pp. 427–430: The Tower of Hanoi

[8] Epp 1995, pp. 447–448: An Explicit Formula for the Tower of Hanoi Sequence

[9] Wirth 1976, p. 127

[10] Wirth 1976, p. 127

[11] Mongan, John; Giguère, Eric; Kindler, Noah (2013). Programming Interviews Exposed: Secrets to Landing Your Next Job (3rd ed.). Wiley. p. 115. ISBN 978-1-118-26136-1. https://archive.org/details/programminginter00mong_658.

[12] Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 79, ISBN 9781430232384.

[13] Drozdek, Adam (2012), Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017.

[14] Shivers, Olin. "The Anatomy of a Loop - A story of scope and control" (PDF). Georgia Institute of Technology. Retrieved 2012-09-03.

[15] Lambda the Ultimate. "The Anatomy of a Loop". Lambda the Ultimate. Retrieved 2012-09-03.

[16] "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation". Docs.python.org. Retrieved 2012-09-03.

[17] Krauss, Kirk J. (2014). "Matching Wildcards: An Empirical Way to Tame an Algorithm". Dr. Dobb's Journal.

[18] Mueller, Oliver (2012). "Anatomy of a Stack Smashing Attack and How GCC Prevents It". Dr. Dobb's Journal.

[19] "StackOverflowException Class". .NET Framework Class Library. Microsoft Developer Network. 2018.

[20] "Depth First Search (DFS): Iterative and Recursive Implementation". Techie Delight. 2018.

[21] Mitrovic, Ivan. "Replace Recursion with Iteration". ThoughtWorks.

[22] La, Woong Gyu (2015). "How to replace recursive functions using stack and while-loop to avoid the stack-overflow". CodeProject.

[23] Moertel, Tom (2013). "Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick".

[24] Salz, Rich (1991). "wildmat.c". GitHub.

[25] Krauss, Kirk J. (2008). "Matching Wildcards: An Algorithm". Dr. Dobb's Journal.

[26] Krauss, Kirk J. (2018). "Matching Wildcards: An Improved Algorithm for Big Data". Develop for Performance.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

递归