尾递归如何改变大 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的文档说第一个是O(n(，但第二个是在恒定空间中运行的。

Answer 1

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

另请注意，Racket 已命名为 let，它允许您将尾递归形式写得更好一点

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

球拍还支持通过匹配进行模式匹配

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

Answer 2

我想我现在明白了。这是关于空间(RAM(的复杂性，而不是时间复杂性。