理解尾递归向量 [英] Understanding a tail-recursive vector

问题描述

我有一个尾递归函数，可以将向量转换为列表.我单独理解每一行，但有几个问题:

I have a tail-recursive function which converts a vector into a list. I understand each line individually, but have a couple questions:

首先，在代码中cons ((vector-ref v i) r) (- i 1) 是什么意思?(标记为Q1".)我知道它需要向量 v 的第 i 个元素并将它与 i-1 连接起来，但是为什么必须是 i-1?为什么不使用 i+1?例如如果向量 v 长度总共为 5，则元素编号 5 与编号 4 连接.我知道它正在制作向量列表，但为什么要使用 i-1(减少)?谁能给我一个解释?

Firstly, in the code what does the code cons ((vector-ref v i) r) (- i 1) mean? (Marked "Q1".) I know that it takes the i'th element of vector v and concatenates it with i-1, but why have to be i-1? Why not work with i+1? e.g. if the vector v length is total 5, then element number 5 is concatenated with the number 4. I understand that it is making the vector list, but why work with i-1 (reducing)? Can anyone give me an explanation?

(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 (cons (vector-ref v (- (vector-length v) 1)) '()) (- (vector-length v) 2))
      '()))))

推荐答案

i 每次调用减少的原因是 i 用于确定我们什么时候已经到达向量的末尾.这个想法是，当我们最初调用 helper 函数时，我们将 i 设置为向量的长度(减去 2)，然后在每次递归调用中减少 i 乘以 1，直到它小于 0，此时我们知道我们已经遍历了整个向量.

The reason why i is decreasing with each call is that i is used to determine when we've reached the end of the vector. The idea is that when we call the helper function initially, we set i to be the length of the vector (minus 2), and then in each recursive call decrease i by 1 until it becomes less than 0, at which point we know that we've gone through the whole vector.

我相信，导致您困惑的问题是您对 cons 调用的解析不正确 - 计算括号向我们表明该调用确实是 (cons (vector-ref vi) r) - (- i 1) 只是 helper 的第三个参数.

The issue causing your confusion, I believe, is that you're parsing the cons call incorrectly- counting the parentheses shows us that the call is really (cons (vector-ref v i) r) - the (- i 1) is just the third argument to helper.

最后，在第 9 行检查向量长度大于 0 的想法是，如果向量的长度为 0，我们只想返回一个空列表 '();如果我们不做这个检查，那么对 (vector-ref v (- (vector-length v) 1)) 的调用将变成 (vector-ref v -1) 如果我们输入一个空向量，这显然会失败.我不确定您所说的总长度检查"是什么意思，但是 (vector-length v) 确实返回了 v 的整个长度.

Finally, the idea of checking in line 9 that the length of the vector is greater than 0 is that if the vector's length is 0, we just want to return an empty list '(); if we didn't do this check, then the call to (vector-ref v (- (vector-length v) 1)) would become (vector-ref v -1) if we input an empty vector, which would obviously fail. I'm not sure what you mean by "total length checking", but (vector-length v) does indeed return the entire length of v.

这篇关于理解尾递归向量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！