示例：计算数n的阶乘
先看看被拿来做反面教材的线性递归：
> (define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
瞧一瞧它都干了些什么事儿吧：
| 1 |
(factorial 4) |
| 2 |
(* 4 (factorial 3)) |
| 3 |
(* 4 (* 3 (factorial 2))) |
| 4 |
(* 4 (* 3 (* 2 (factorial 1)))) |
| 5 |
(* 4 (* 3 (* 2 1)))) |
| 6 |
(* 4 (* 3 2)) |
| 7 |
(* 4 6) |
| 8 |
24 |
再来看看传说中的尾递归：
> (define (factorial n)
;; (fact-iter)才是递归函数：
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
;; 这里第一次调用递归函数：
(fact-iter 1 1 n))
不必怀疑，这里的递归函数是fact-iter，我只是把它放到了factorial中去描述，这样factorial就可是成一个独立的函数了。来看看它是怎么做的：
| 1 |
(factorial 4) |
| 2 |
(fact-iter1 1 4) |
| 3 |
(fact-iter1 2 4) |
| 4 |
(fact-iter2 3 4) |
| 5 |
(fact-iter6 4 4) |
| 6 |
(fact-iter24 5 4) |
| 7 |
24 |
注解：看了示例，不说也明白，线性递归时，过程中计算式是先展开而后收缩；尾递归则是从头到尾都保持着一样的身材，不得不说这货保养好。
为什么会出现两种不同的情况呢？从第一种来看，这厮不管好歹，只要有是传给它的值，便直接留到它下辈子一并处理，典型的懒汉。第二个式子则勤劳多了，传给它的值，它先计算一翻，谋划下该留给下辈子些什么东西，如此下辈子只管那时该做的事，做完后再把下下辈子需做的事计划一翻即可。所谓没有债务一身轻，就是这道理了。
好吧，解释下尾递归fact-iter的计算方式。首先从参数说起：
| product |
每一次执行fact-iter后计算的值 |
| counter |
计数器，类中其它语言for (int i= 0; i< n; i++)中的i。 |
| max-count |
计数的最大值，类中其它语言for (int i= 0; i< n; i++)中的n。 |
对于fact-iter，每一次运算后，都把结果存在product中，并把counter+1做为下次计算的参数。当递归到了尽头时，fact-iter算便直接返回product的值就可以了。
备注：示例来自《计算机程序的构造和解释中文版2》1.2小节。