方案：使用遞歸填充矢量？

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); 
} 

希望這有助於！