尾递归思想

使用递归可以轻松的写出计算阶乘的代码，比如下面这段我用Racket编写的Scheme代码

#lang scheme

(define (factorial n)

  ( if (= n 1)

       1

       (* n (factorial (- n 1)))))

(factorial 5)

这样写有什么问题呢？从上面的表达式可以发现在计算factorial(n)之前必须先计算factorial(n-1)，而factorial 的递归调用并不是函数的最后一个调用（上面这个factorial 函数的最后调用应该是乘法 ），所以在计算factorial(n)之前必须先求值出factorial(n-1)并且到保存临时结果，所以上面程序的空间复杂度是n

使用尾递归思想就是让函数对自身的调用变为函数的最后一个调用

同样的scheme代码

(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-count)))

(factorial 5)

观察上面的代码我们会发现fact-iter函数再进行自身调用的时候是处于函数的最后一个调用，所以fact-iter函数的返回值不需要被临时保存，有点类似于数据单向传递的思想，所以编译器或者解释器只要维护三个用于临时存储fact-iter product counter max-count 的空间就可以了，该方法的空间复杂度为常数

普通递归求斐波那契数列

#lang scheme

(define (fib n)

  (cond ((= n 0) 0)

        ((= n 1) 1)

        (else (+ (fib (- n 1))

                 (fib (- n 2))))))

(fib 10)

尾递归风格

(define (fib n)

  (define (fib-iter a b count)

  (if (= count 0)

      a

      (fib-iter b

                (+ a b)

                (- count 1))))

  (fib-iter 0 1 n))

(fib 10)