递归 (计算机科学)

递回（英语：recursion）在电脑科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。 递回式方法可以被用于解决很多的电脑科学问题，因此它是电脑科学中十分重要的一个概念。 绝大多数程式语言支援函式的自呼叫，在这些语言中函式可以通过呼叫自身来进行递回。计算理论可以证明递回的作用可以完全取代回圈，因此有很多在函数程式语言（如Scheme）中用递归来取代循环的例子。

电脑科学家尼克劳斯·维尔特如此描述递回：

递回的强大之处在于它允许使用者用有限的语句描述无限的物件。因此，在电脑科学中，递回可以被用来描述无限步的运算，尽管描述运算的程式是有限的。

——尼克劳斯·维尔特

递回程式

java

public void recursiveTest(){
    recursiveTest();  //自己调用自己，就叫递归
}

python

def RecursiveTest():
    RecursiveTest()  # 自己调用自己

以上两个程式是最简单的递归，但因为无限地调用自己而不会停下，就会因为栈空间溢出而导致程序产生异常而强制停止，而python会因为自身设置的保护措施（限定递归的循环次数，但该次数可更改）而不断抛出异常。

所以如果想要设计一个递归程式，就必须注意设定一个表达式判断（例如if语句）来告诉程序是否应该继续递归下去。

应用

在支援自呼叫的程式语言中，递回可以通过简单的函式呼叫来完成，如计算阶乘的程式在数学上可以定义为：

$\operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}$

这一程式在Scheme语言中可以写作：

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

不动点组合子

主条目：不动点组合子

即使一个程式语言不支援自呼叫，如果在这语言中函式是头等物件（即可以在执行期创建并作为变数处理），递回可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程式没有用到自呼叫，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递回的目的。

(define Z
  (lambda (f)
    ((lambda (recur) (f (lambda arg (apply (recur recur) arg))))
     (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))

(define fact
  (Z (lambda (f)
       (lambda (n)
         (if (<= n 0)
             1
             (* n (f (- n 1))))))))

这一程式思路是，既然在这里函式不能呼叫其自身，我们可以用 Z 组合子应用(application)这个函式后得到的函式再应用需计算的参数。

尾端递回

主条目：尾端递回

尾端递回是指递回函式在呼叫自身后直接传回其值，而不对其再加运算。尾端递回与回圈是等价的，而且在一些语言（如Scheme中）可以被优化为回圈指令。 因此，在这些语言中尾端递回不会占用呼叫堆叠空间。以下Scheme程式同样计算一个数字的阶乘，但是使用尾端递回：

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))

能够解决的问题

1、数据的定义是按递归定义的。如费氏数列。

2、问题解法按递归算法实现。如汉诺塔。

3、数据的结构形式是按递归定义的。如二叉树、广义表等。

递回资料

主条目：递归数据类型

资料型别可以通过递回来进行定义，比如一个简单的递回定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”。Haskell中可以定义连结串列为：

data ListOfStrings = EmptyList | Cons String ListOfStrings

这一定义相当于宣告“一个连结串列或是空串列，或是一个连结串列之前加上一个字串”。可以看出所有连结串列都可以通过这一递回定义来达到。