尾递归如何改变大O？

Question

没有尾部优化：

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

结果：

(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

尾部优化：

(define (my-length lst)
  ; local function iter:
  (define (iter lst len)
    (cond
     [(empty? lst) len]
     [else (iter (rest lst) (+ len 1))]))
  ; body of my-length calls iter:
  (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 (list) 3)
3

大O如何改善？ Racket's docs说第一个是O（n），但第二个是在恒定的空间中运行。

Answer 1

你是对的。尾部递归实现不能保证节省时间，而是保证节省空间 - 堆栈不会增长

还要注意，Racket有named let，它允许你编写尾部递归形式更好一点

(define (length xs)
  (let loop ((xs xs) (len 0))
    (if (empty? xs)
        len
        (loop (cdr xs) (+ 1 len)))))

Racket还通过​​match支持模式匹配

(define (length xs)
  (let loop ((xs xs) (len 0))
    (match xs
      ((cons _ rest) (loop rest (+ 1 len)))
      (empty len))))

Answer 2

我想我现在明白了。这是关于空间（RAM）复杂性而不是时​​间复杂性。