递归算法科普一

在计算机科学中，递归是一种解决问题的方法，其中解决方案依赖于同一问题的较小实例的解决方案。这类问题通常可以通过迭代来解决，但这需要在编程时识别和索引较小的实例。递归通过使用在自己的代码中调用自己的函数来解决这种递归问题。

这种方法可以应用于许多类型的问题，递归是计算机科学的核心思想之一

递归的力量显然在于可以用一个有限语句定义一个无限的对象集。同样地，一个有限的递归程序可以描述无限多的计算，即使这个程序不包含显式重复。

- Niklaus Wirth，算法+数据结构=程序，1976

大多数计算机编程语言都支持递归，允许函数从自己的代码中调用自己。一些函数式编程语言。不要定义任何循环结构，而只依赖递归来反复调用代码。可计算性理论证明了这些纯递归语言是图灵完备的，这意味着它们与基于while和for等控制结构的命令式语言一样强大（它们可以用来解决相同的问题）。

从内部反复调用函数可能会导致调用堆栈的大小等于所有相关调用的输入大小之和。因此，对于可以通过迭代很容易解决的问题，递归通常效率较低，对于大型问题，使用诸如尾部调用优化之类的优化技术是非常重要的。

递归函数与算法

计算机编程的一种常见策略是将问题分为与原始问题相同的子问题，解决这些子问题，并将结果结合起来。这通常被称为分治方法；当与存储解决子问题结果的查找表结合使用时（避免重复求解这些问题并产生额外的计算时间），则可称为动态编程或回忆录。

递归函数定义有一个或多个基本情况，即输入，其中函数生成的结果很小（不重复），以及一个或多个递归情况，即程序递归（调用自己）的输入。例如，因子函数可以由方程0递归定义！=1，对于所有n>0，n！=n（n−1）！。方程本身都不是一个完整的定义；第一个是基情况，第二个是递归情况。由于基用例打破了递归的链，所以有时也称为“终止案例”。

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

对于某些函数（例如，计算e=1/0的序列的函数）！+1/1！+1/2！+1/3！+…）输入数据没有明显的基情况；对于这些情况，可以添加参数（例如在我们的系列示例中要添加的术语的数量），以提供建立基情况的“停止标准”。这样的例子更自然地被corecursion处理，其中输出中的连续项是部分和；通过使用索引参数表示“计算第n个项（n部分和）”，可以将其转换为递归。

递归数据类型

许多计算机程序必须处理或生成任意数量的数据。递归是一种表示程序员不知道其确切大小的数据的技术：程序员可以用自引用定义来指定这些数据。有两种类型的自我参照定义：归纳定义和共同定义。

归纳定义数据

归纳定义的递归数据定义是指定如何构造数据实例的定义。例如，可以归纳地定义链表

data ListOfStrings = EmptyList | Cons String ListOfStrings

上面的代码指定字符串列表为空，或者指定包含字符串和字符串列表的结构。定义中的自引用允许构造任何（有限）个字符串的列表。

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

A natural number is either 1 or n+1, where n is a natural number.

类似地，递归定义经常被用来为编程语言中的表达式和语句的结构建模。语言设计者通常用一种语法来表达语法，例如Backus–Naur form；这里有这样一种语法，对于一种简单的算术表达式语言，它有乘法和加法：

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

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

共同定义的数据和核心词汇

共归纳数据定义是指定可以对一段数据执行的操作的定义；通常，自引用共归纳定义用于无限大的数据结构。

非正式地给出的无限字符串流的共同归纳定义可能如下所示：

A stream of strings is an object s such that:
 head(s) is a string, and
 tail(s) is a stream of strings.

这与字符串列表的归纳定义非常相似；不同之处在于，该定义指定了如何通过访问器函数head和tail访问数据结构的内容，以及这些内容可能是什么，而归纳定义指定了如何创建结构以及可以创建什么从。

corecurson与coinduction相关，可以用来计算（可能）无限对象的特定实例。作为一种编程技术，它最常用于惰性编程语言的上下文中，当程序输出的期望大小或精度未知时，它比递归更好。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个获取结果有限部分的机制。计算前n个素数的问题是一个可以用corecursive程序（例如这里）解决的问题。

递归类型

单递归与多递归

只包含一个自引用的递归称为单递归，而包含多个自引用的递归称为多个递归。单个递归的标准示例包括列表遍历（例如在线性搜索中）或计算阶乘函数，而多个递归的标准示例包括树遍历，例如在深度优先搜索中。

单次递归通常比多次递归更有效，通常可以用迭代计算代替，迭代计算在线性时间内运行，需要恒定的空间。相比之下，多重递归可能需要指数时间和空间，而且更基本上是递归的，如果没有显式堆栈，无法用迭代代替。

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

间接递归

递归的大多数基本示例和这里介绍的大多数示例都演示了直接递归，即函数调用自身。当一个函数不是由它自己调用，而是由它调用的另一个函数（直接或间接）调用时，就会发生间接递归。例如，如果f调用f，这是直接递归，但如果f调用g调用f，则这是f的间接递归。可以有三个或更多函数的链；例如，函数1调用函数2，函数2调用函数3，函数3再次调用函数1。

间接递归也被称为相互递归，这是一个更为对称的术语，尽管这只是强调的不同，而不是不同的概念。也就是说，如果f调用g，然后g调用f，而f又调用g，从f本身的角度来看，f是间接递归的，而从g的角度来看，f是间接递归的，而从两者的角度来看，f和g是相互递归的。类似地，一组三个或三个以上互相调用的函数可以称为一组相互递归的函数。

匿名递归

递归通常通过按名称显式调用函数来完成。然而，递归也可以通过基于当前上下文隐式调用函数来完成，这对于匿名函数特别有用，称为匿名递归。

结构递归与生成递归

一些作者将递归分为“结构性”或“生成性”。这种区别与递归过程从何处获取其工作的数据以及如何处理这些数据有关：

使用结构化数据的函数]通常将参数分解为直接的结构组件，然后处理这些组件。如果其中一个直接组件与输入属于同一类数据，则该函数是递归的。因此，我们将这些函数称为（结构上）递归函数。

-程序设计，Krishnat，2001

因此，从结构上讲，对每个递归字段的调用都是递归函数的一个特征。结构递归包括几乎所有的树遍历，包括XML处理、二叉树的创建和搜索等。考虑到自然数的代数结构（即自然数不是零，就是自然数的后继数），因式等函数也可以看作是结构递归。

生成递归是另一种选择：

许多著名的递归算法从给定的数据中生成一个全新的数据并在其上重复。HtDP（如何设计程序）将这种方法称为生成递归。生成递归的例子包括：gcd、快速排序、二进制搜索、mergesort、牛顿法、分形和自适应积分。

具体算法讲解可参考这篇文章：Java递归方法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

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

这种递归关系的计算说明了在计算上述伪代码时将执行的计算：

b4           = 4 * b3

             = 4 * (3 * b2)
             = 4 * (3 * (2 * b1))
             = 4 * (3 * (2 * (1 * b0)))
             = 4 * (3 * (2 * (1 * 1)))
             = 4 * (3 * (2 * 1))
             = 4 * (3 * 2)
             = 4 * 6
             = 24

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

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

上面的命令代码相当于使用累加器变量t的数学定义：

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

最大公约数

计算两个整数的最大公约数的欧几里德算法可以递归编写。

函数定义：

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

最大公约数的递归关系，其中x\%y表示x/y的余数：

Computing the recurrence relation for x = 27 and y = 9:
gcd(27, 9)   = gcd(9, 27% 9)
             = gcd(9, 0)
             = 9

Computing the recurrence relation for x = 111 and 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

上面的递归程序是tail recursive；它相当于一个迭代算法，上面所示的计算显示了由消除尾部调用的语言执行的求值步骤。下面是一个不适合使用尾部语言的显式迭代算法。通过将其状态完全保持在变量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

迭代算法需要一个临时变量，即使已知欧几里德算法的知识，也很难通过简单的检查来理解过程，尽管这两个算法的步骤非常相似。

河內之塔

河内的塔楼是一个数学难题，它的解说明了递归性。

有三个木桩可以存放不同直径的圆盘。一个较大的磁盘可能永远不会堆叠在较小的磁盘上。从一个挂钩上的n个磁盘开始，它们必须一次移动到另一个挂钩。移动堆栈的最小步骤数是多少？

功能定义：

河内的递推关系：

Computing the recurrence relation for n = 4:
hanoi(4)     = 2*hanoi(3) + 1
             = 2*(2*hanoi(2) + 1) + 1
             = 2*(2*(2*hanoi(1) + 1) + 1) + 1
             = 2*(2*(2*1 + 1) + 1) + 1
             = 2*(2*(3) + 1) + 1
             = 2*(7) + 1
             = 15

实现示例：

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塔序列可以简化为一个显式公式

河内塔的显式公式：

h1 = 1   = 21 - 1
h2 = 3   = 22 - 1
h3 = 7   = 23 - 1
h4 = 15  = 24 - 1
h5 = 31  = 25 - 1
h6 = 63  = 26 - 1
h7 = 127 = 27 - 1
In general:
hn = 2n - 1, for all n >= 1

二进制搜索

二进制搜索算法是一种在排序数组中搜索单个元素的方法，每次递归将数组对半。诀窍是在数组中心附近选取一个中点，将该点的数据与正在搜索的数据进行比较，然后对以下三个可能的条件之一作出响应：数据在中点处找到，中点处的数据大于正在搜索的数据，或中点处的数据小于正在搜索的数据因为。

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

在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

 */
 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
 */
 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);
 }