方案：使用递归填充矢量？

Question

我是新来的计划 - 我目前正在尝试学习语法和如何递归思考。我来到一个向量部分，并希望能够通过某种循环（当然使用递归）在我的向量中设置值。我有这个变量：

(define my-vector (make-vector 5)) 

然后，我想使用vector-set!过程填充。通常，在C++（只有其他语言我真正熟悉），这将迭代的方式进行，例如

//... 

std::vector<int> myVector; 

for(int i = 0; i < 5; ++i) // populate the vector 
    myVector.push_back(i); 

std::vector<int>::const_iterator outIter; 

for(outIter = myVector.begin(); 
    outIter != myVector.end(); ++outIter) 
    std::cout << *outIter << " "; 

std::cout << std::endl; 

//... 

但是，我知道，这种事情应该通过递归方案来完成。什么是递归的populate-vector程序可能看起来像？

Answer 1

(let f ((i 0)) 
    (when (< i 5) 
    (vector-set! my-vector i i) 
    (f (+ i 1)))) 

您可以在线试用here。

您也可以尝试使用DO语法，但大多数觉得很难记住:)

学习使用命名LET是非常重要的。

另请注意，Scheme矢量只是一个固定大小的数组。

Answer 2

一个办法是这样的：

void PopulateVector(vector<int>& vec, int n) { 
    if (n < 0) return; 

    PopulateVector(vec, n - 1); 

    vec.push_back(n); 
} 

的思路如下。首先，如果你想创建一个值为0到某个负数的向量，我们什么也不做;没有要添加的值。否则，我们首先填充值为0到n - 1的向量，然后将n附加到向量中。

请注意，这是一个非常低效的内存使用程序;它需要调用堆栈的线性内存。迭代版本可能会更好。我们可以将此函数重写为尾递归，并希望优化器消除递归，但不能保证会发生这种情况（同时，Scheme需要IIRC，尾部呼叫消除）。这个想法是使用包装函数，以便我们可以计数到n而不是从n减少：

void PopulateVector(vector<int>& vec, int n) { 
    if (n < 0) return; 

    PopulateVectorRec(vec, 0, n); 
} 

void PopulateVectorRec(vector<int>& vec, int current, int n) { 
    if (current > n) return; 

    vec.push_back(current); 

    PopulateVectorRec(vec, current + 1, n); 
} 

希望这有助于！