递归与迭代

1. 过程定义与计算过程

当我们说一个过程是递归的时候，论述的是一个语法形式上的事实，说明这个过程的定义中(直接或间接地)引用了该过程本身。

但递归定义可以产生不同的计算过程，比如下面定义的+，其在定义时都递归的调用了自己:

(define (+ x y)
    (if ( = x 0)
        y
        (+ (-1 x) (+1 y))))


; 运用代换模型

(+ 3 4)
(+ 2 5)
(+ 1 6)
(+ 0 7)
7

我们可以看到，虽然采用了递归的定义，但其在实际运算时，函数调用的直接返回自身的另一个调用，每个层返回的调用都保留得出结果的完整信息，而且在最后一层会直接得出结果，(如果语言的实现支持尾递归优化)它循环结构有相同的时间复杂和空间复杂度(time(x) = θ(x); space(x) = θ(1))。

(define (+ x y)
    (if (= x 0)
        y
        (+1 (+ (-1 x) y)))

; 运用代换模型

(+ 3 4)
(+1 (+ 2 4))
(+1 (+1 (+ 1 4)))
(+1 (+1 (+1 (+ 0 4))))
(+1 (+1 (+1 4)))
(+1 (+1 5))
(+1 6)
7

而这次，同样采用递归的定义，其在实际运算时，函数一层一层调用，最后一层会返回的结果会参与上一层的运算，最终结果要在第一层计算出并返回，其时间复杂度(time(x) = θ(x)，空间复杂度space(x) = θ(x))。

综上，计算过程是否为递归或迭代不在于定义方式，递归的定义也可以产生迭代的运行过程，其区别在于:

实际运行时，递归调用的函数在结束时是否直接返回值，如果直接返回，则为迭代计算过程；如果返回值给其上一层函数并参与运算，则为递归计算过程。
迭代的运行过程的每一层函数都会保存有得出结果的所有状态，而递归的计算过程还存在一些“隐含”的信息。

2. 尾递归

尾递归是编程语言实现的一种特性，这个特性为可以在常量空间内执行迭代计算过程，即使这个计算过程是用一个递归过程描述的。具有这一特性的实现称为尾递归的。

实际上，尾递归优化可以使尾递归调用在常量空间内做迭代计算。（William Clinger博士在Compiler Optimization for Symbolic Languages中引征Guy Steel的话：“并不是函数调用造成压栈，是参数求值造成压栈。”）

普通的递归:

; n! = n * (n-1)!

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

; 运用代换模型

(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

尾递归版本:

; n! = n * n-1 * ... * 1
; n! = 1 * n * n-1 * ... * 1
;
; product = 1
; counter = n
; loop:
;     if counter == 0:
;         break
;     product = product * counter
;     counter = counter - 1

(define (factorial n)

    (define (fact-iter counter product)
        (if (= counter 0)
            product
            (fact-iter (- counter 1) (* product counter))))

    (fact-iter n 1))

; 运用代换模型

(factorial 3)
(fact-iter 3 1)
(fact-iter 2 3)
(fact-iter 1 6)
(fact-iter 0 6)
6

尾递归优化可以将尾递归改为迭代表达:

n! = n * n-1 * ... * 1
n! = 1 * n * n-1 * ... * 1

product = 1
counter = n
loop:
    product = product * counter
    counter = counter - 1
    if counter == 0:
        break

即我们可以写出递归定义的迭代计算过程，但如果语言的实现不支持尾递归优化，得到的过程仍然会每一次调用时申请新的栈空间，而不是像循环一样更新原有值。所以我们是否可以使用尾递归，还得看所用语言是否支持尾递归优化。

older
Newer