尾递归如何改变算法的大O复杂度？

让我们通过计算列表长度的例子，直观对比未做尾优化和做了尾优化的递归实现差异，搞清楚尾优化到底解决了什么问题。

未进行尾优化的实现 #

先看这个最直观的递归版本：

(define (my-length lst)
  (cond [(empty? lst) 0]
        [else (+ 1 (my-length (rest lst)))]))

它的计算过程是层层展开的，每一次递归调用后都得等着结果回来才能执行+1操作：

(my-length (list "a" "b" "c")) 
= (+ 1 (my-length (list "b" "c"))) 
= (+ 1 (+ 1 (my-length (list "c")))) 
= (+ 1 (+ 1 (+ 1 (my-length (list))))) 
= (+ 1 (+ 1 (+ 1 0))) 
= (+ 1 (+ 1 1)) 
= (+ 1 2) 
= 3

这个版本的问题在于：每一层递归都需要在调用栈里保留一个栈帧，等着下一层的计算结果返回后完成+1。如果列表特别长，调用栈会越来越深，最终可能导致栈溢出。

尾优化后的实现 #

尾优化的核心思路是把中间计算结果作为参数传递给递归函数，让递归调用成为函数的最后一个操作，这样解释器就可以重用当前的栈帧，不用额外占用空间。

优化后的代码是这样的：

(define (my-length lst)
  ; 定义局部迭代函数，负责携带当前已计算的长度
  (define (iter lst len)
    (cond [(empty? lst) len]
          [else (iter (rest lst) (+ len 1))]))
  ; 初始调用时，已计算长度为0
  (iter lst 0))

它的计算过程就简洁多了，每一步都是直接进入下一次递归，没有后续的等待操作：

(my-length (list "a" "b" "c"))
= (iter (list "a" "b" "c") 0)
= (iter (list "b" "c") 1)
= (iter (list "c") 2)
= (iter '() 3)
= 3

这里的iter函数每次递归调用都是整个函数的最后一步操作（尾调用），Scheme解释器会识别这种模式，直接复用当前栈帧，不管列表多长，栈的占用量都是恒定的，彻底避免了栈溢出的风险。

内容的提问来源于stack exchange，提问作者HappyFace