定义

递归：

一个过程是递归 (recursive) 的， 也就是: 在过程的定义中（直接或间接地）引用了该过程本身。

尾递归是递归调用的一种实现：

尾递归是递归调用的一种实现，如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归 (tail-recursive) 的。

理解

先来看一个简单的例子

计算阶乘的函数：

1
2
3
4
(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))
1
2
3
4
5
6
7
8
(define (factorial n)
    (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter (*counter product)
                   (+ counter 1)
                   max-counter)))

可以看的，第一种实现是一个简单的递归过程。第二种实现则是一个尾递归的过程，在函数 fact-iter 中，仅在函数末尾出现自身调用。

先来看一下这两种实现的执行过程:

第一种实现：

1
2
3
4
5
6
7
8
9
10
11
12
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

第二种实现：

1
2
3
4
5
6
7
8
9
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

我们可以看的，第一种实现需要用线性增长的空间存储信息，第二种则只需维持固定的变量。

在 SICP (Structure and Interpretation of Computer Programs) 中，尾递归形式的实现称为迭代 (iterative ) 过程。

在一般的认识 (语言) 中，迭代过程是循环结构实现，也就是通过 for，while 等特殊语法。而Lisp等语言并不支持循环语句。

我们可以简单地把尾递归转化为一个循环过程

1
2
3
4
5
6
7
8
9
int factorial(int max_count)
{
    int product = 1;
    for(int counter = 1; counter <= max_count; counter += 1)
    {
        product = counter * product;
    }
    return product;
}

换句话说，循环语句都可以通过一个尾递归实现。

看一下 SICP里是怎么说的

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ‘’looping constructs’’ such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar

emmm 有点绕，解释一下。在 SICP 中，我们说一个程序是递归的，指的是在程序定义中引用了程序本身。而一个递归的程序的计算过程是迭代的，则是说解释器在执行是只需要保持固定数量的状态变量。它确实是 iterative。

然而，在很多语言中 (如C，python)，对于尾递归形式的函数，它依然是以递归的形式执行，也就是他需要存储量与过程调用的次数成正比。因此，要实现迭代过程，需要使用for，while 等循环语句。

通过尾递归的实现，我们可以利用常规的递归机制表述迭代过程，各种迭代结果不过是一些 “syntactic sugar”.

树形递归

有些时候我们需要在定义中多次调用自身，可以称为树形递归 (tree recursion): 它的展开过程像一颗树。考虑斐波那契数列的递归过程：

1
2
3
4
5
(define (fib n)
    (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

[图源 SICP Figure 1.5]

image-20200114121355835

一般来说，树形递归计算所需的步骤数正比于树中结点数，空间需求正比于树的最大深度。

我们可以用尾递归实现效率更高的方式：

1
2
3
4
5
6
(define (fib n)
  (fib-iter 1 0 n))
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

它也是迭代过程：

1
2
3
4
5
6
7
8
9
10
int fib(int count)
{
    int a = 1, b = 0;
    for(; count > 0; count -= 1)
    {
        a = a+b;
        b = a;
    }
    return b;
}

递归，尾递归与迭代实际上是可以相互转换的。

一些神奇的例子

1.欧几里得算法求最大公约数

这是一个直观的尾递归算法

1
2
3
4
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

2. 尾递归实现

用尾递归过程实现

$$
f(n) = n, n < 3\
f(n) = f(n-1)+2f(n-2)+3f(n-3),n\ge 3
$$

用递归其实很简单(定义就是递归的)，下面是尾递归的实现：

答案参考: http://community.schemewiki.org/?sicp-ex-1.11 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 (define (f n) 
   ;; Given starting coefficients (a, b, c) = (1, 2, 3), 
   ;; where f(n) = 1 f(n-1) + 2 f(n-2) + 3 f(n-3), 
   ;; f-iter calculates new (a, b, c) such that 
   ;; f(n) = a f(2) + b f(1) + c f(0), 
   ;; where integer n > 3. 
   ;; main body 
   (if (< n 3) 
       n 
       (f-iter n 1 2 3))) 
(define (f-iter n a b c) 
   (if (= n 3) 
      (+ (* a 2)  ;; f(2) = 2 
      (* b 1)  ;; f(1) = 1 ;; (* b 1) = b, and 
      (* c 0)) ;; f(0) = 0 ;; (* c 0) = 0, which can be omitted, 
                                 ;; but shown here for completeness. 
      (f-iter (- n 1)       ;; decrement counter 
              (+ b a)       ;; new-a = a + b 
              (+ c (* 2 a)) ;; new-b = 2a + c 
              (* 3 a))))    ;; new-c = 3a

or

1
2
3
4
5
6
7
8
(define (fi n) 
     (f-iter 0 1 2 n)) 
(define (f-iter a b c count) 
     (cond ((< count 0) count) 
          ((= count 0) a) 
          ((= count 1) b) 
          ((= count 2) c) 
     (else (f-iter b c (+ c (* 2 b) (* 3 a)) (- count 1)))))

3. 素数检测

判断一个自然数 $n$ 是不是素数，自然的方法是从2到 $\sqrt{n}$ 检查是否为 $n$ 的因数。用递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
(define (smallest-divisor n);;找到最小的因数
  (find-divisor n 2));;从 2 开始
(define (find-divisor n test-divisor);;它是尾递归的
  (cond ((> (square test-divisor) n) n)	;;test-divisor平方大于n
                                        ;;停止搜索，因数为n
        ((divides? test-divisor n) test-divisor);;可以整除，因数为 test-divisor
        (else (find-divisor n (+ test-divisor 1)))));;不能整除，test-divisor加一
(define (divides? a b)	;;整除
  (= (remainder b a) 0))

(define (prime? n)				
  (= n (smallest-divisor n)));;若最小的因数为 n， 是一个素数

关系

尾递归是递归的一种实现方式，即函数中递归形式的调用都出现在函数的末尾。尾递归实际上与迭代等效。在Lisp等语言中，尾递归会被解释器通过迭代进行计算。

用尾递归的形式实现递归，需要用有限的变量表示当前状态，通过修改变量逐步满足条件。

用尾递归实现迭代(循环)，实际上时间迭代的判断放在递归函数的变量中，在递归函数中进行变量的修改与条件判断，同时在主函数中调用递归函数。

尾递归优化

像上面所说的，一些编译器会对尾递归进行优化，从而使用固定的内存空间。称为 TRO (Tail recursion optimization 尾递归优化) 或 TCE (Tail Call elimination 尾递归消除)

还没有很懂 orz

编译器做的事情是：检测到一个尾递归后，在函数前加上 start ，函数结尾处加上 goto start，就实现了将尾递归转化为迭代。

这里说一个下面链接中实现 CPython实现TRO的方法：

  1. 确定”安全的”尾递归调用。
    应该是一个 CALL操作与RETURN操作连续，并且完全在任何try块之外的代码块。
    （注意：这里忽略了不同的CALL_ *操作码，使用相同的方法应该很容易处理。）
  2. 接下来，将每个这样的CALL-RETURN操作对替换为一个CALL_RETURN操作。
    如果在运行时确定此特定调用不适用于TRE，则将执行CALL的常规操作，然后执行RETURN操作。

不进行TRO

事实上，很多语言不支持尾递归优化，python 的创造者做出了一些解释：http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

他认为：

  1. TRE与堆栈跟踪不兼容：消除尾部递归后，没有堆栈框架可用于打印回溯，并使调试变得困难。
  2. 关于TRE仅仅是一个优化的想法是错误的。一旦消除了尾部递归，开发人员将开始编写依赖于它的代码，他们的代码将难以在不提供尾递归的实现上运行。
  3. 递归不是所有编程的基础。

作者还给出了很多对于python支持尾递归优化的做法，当然他都不持肯定态度：

Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop?

(After all TRE only addresses recursion that can easily be replaced by a loop. :-)