0

最初我发布了一个问题“了解尾递归向量-> 列表答案”，这是附加问题。我对方案的一般理解真的很模糊。所以我现在还有几个问题：

;;;;;; 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）尾递归，这让我真的很难理解。我理解他们为什么需要尾递归，并且基本上他们使用它来避免迭代，所以他们使用帮助程序作为中间例程..所以他们可以避免将每次迭代放入堆栈......这样的事情。和 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之外......？）。

4

1 回答 1

2

First off, I would have rewritten you example a little, to this:

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

And to see the difference lets make the non tail-recursive version:

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

There is no loop functionality in Scheme. It's only recursion and recursion that does not grow the stack, because there is more to do in the previous step, is called tail recursion.

Since we can iterate a vector in any way (it's O(1) access) we can iterate it last to first or first to last. Since a list can only be made last to first the non tail-recursive version won't apply cons on the first element until it has made the whole list except the first element. This makes a 5 element vector to have 5 continuations when hitting the base case. If it were a large vector it can result in a stack overflow.

The first example make the list consisting of the last element first and when it's done it recurses. It does not need to cons anything since the consing was done before the recursion. It's not every problem that can be dealt with like this. Imagine you want to copy a list. It can be iterated from beginning to end but built up from end to beginning. Without mutation or extra consing there is no way to make such procedure tail recursive.

于 2014-05-09T12:30:34.247 回答