Схема: заполнение вектора с помощью рекурсии?

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;

//...

Однако я знаю, что такого рода вещи должны быть выполнены с помощью рекурсии в Scheme.Как могла бы выглядеть рекурсивная populate-vector процедура ??

Answer 1

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

Вы можете попробовать это онлайн здесь .

Вы также можете попробовать использовать синтаксис 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 к вектору.

Обратите внимание, что это очень неэффективная процедура с точки зрения использования памяти;это требует линейной памяти для стека вызовов.Итерационная версия, вероятно, будет намного лучше.Мы можем переписать эту функцию, чтобы она была хвостовой рекурсивной, и надеемся, что оптимизатор исключит рекурсию, но нет никакой гарантии, что это произойдет (в то время как 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);
}

Надеюсь, это поможет!