理解尾递归2

Question

最初，我发布了一个问题“理解尾部递归向量-

;;;;;; original code ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define vector->list:rec
 (lambda (v)
  (letrec ((helper
      (lambda (vec r i)
        (if (< i 0) 
            r
            (helper vec (cons (vector-ref v i) r) (- i 1))  ;; Q1
            ))))
    (if (> (vector-length v) 0)  ;; line 9
      (helper v                  ;; line 10 
              (cons (vector-ref v (- (vector-length v) 1)) '()) 
              (- (vector-length v) 2))
      '()))))

Q2）尾递归，这让我很难理解。我理解他们为什么需要尾递归，基本上他们用它来避免迭代，所以他们使用helper作为中间例程...所以他们可以避免将每次迭代放入堆栈...类似这样的东西。和letrec/lambda表达式，如下所示：

;;;;;;;;;letrec/lambda express;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (some-procedure...)
  (letrec ((helper (lambda (x) 
               ...
               (if some-test?
                   (helper ...))))) ; recursive call --- Q2-1
       ...
    (helper ...)  ; call to recursive local procedure  ---- Q2-2
  ...))

第Q2-2行：为什么这是“局部递归”“局部”对我来说是递归的中间例程。。。在这里中间意味着我的理解。。

[我的困惑]尾递归是不应该迭代（调用）本身，直到整个程序结束-所以不应该在中间例程...=不应该在助手里面？根据我到目前为止的理解...助手是用于封装在letrec表达式中的中间例程...？。）所以最后只调用自己。（我的意思是...：在letrec之外...？）。

Answer 1

首先，我会把你们的例子改写一下：

(define (vector->list-iter v)  
  (let loop ((i (- (vector-length v) 1)) (acc '()))
    (if (< i 0)
        acc
        (loop (- i 1) (cons (vector-ref v i) acc)))))

为了看到差异，让我们制作非尾递归版本：

(define (vector->list-rec v)
  (define len (vector-length v))
  (let loop ((i 0))
    (if (>= i len)
        '()
        (cons (vector-ref v i) (loop (+ i 1))))))

方案中没有循环功能。只有递归和递归不会增加堆栈，因为在前一步中还有更多的事情要做，称为尾部递归。

因为我们可以以任何方式迭代向量（它是O（1）访问），所以我们可以从最后到第一或从第一到最后进行迭代。由于列表只能从最后一个到第一个，非尾部递归版本在生成除第一个元素外的整个列表之前，不会应用于第一个元素。这使得一个5元素向量在击中基本情况时具有5个连续性。如果是大向量，则可能导致堆栈溢出。

第一个示例首先创建由最后一个元素组成的列表，完成后递归。因为考虑是在递归之前完成的，所以它不需要反对任何东西。并不是每个问题都可以这样处理。假设您想要复制一个列表。它可以从头到尾迭代，但可以从头到尾构建。如果没有变异或额外考虑，就无法使这样的过程尾部递归。