Лучший способ написать рекурсивную функцию в C ++?

Question

Вопрос
Я хотел бы знать, является ли это жизнеспособным способом реализации рекурсии с переменной глубиной, чтобы я мог запускать функцию на каждом шаге и любые лучшие / другие решения проблемы описания.
Описание
Предположим, я хочу иметь функцию, которая заполняет массив либо в шаблоне
x,y,x,y,x,y где x и y - переменные, определенные некоторым алгоритмом
и x,y,z,x,y,z, где x, y и z - переменные, определенные одним и тем же алгоритмом.

Это должно продолжаться для всего числа переменных. Это жизнеспособный способ реализовать это.

void recurse_n(int n)
{
    while(n > 0)
    {
        --n;
        recurse_n(n);
        n = 0;
        // Use algorithm here
    }
}

РЕДАКТИРОВАТЬ: Удален неправильный тип возврата, ранее упомянутый. Brainfart.

Answer 1

Итак, основываясь на вашем комментарии, вы хотите узнать, как лучше всего настроить рекурсивную функцию.То, что вы сделали, будет работать, но оно запутанное и слегка запутанное.Чтобы упростить это, я бы сделал следующее:

void recurse_n(int n) {
    if (n <= 0) {
        // Break-out condition
        return;
    }

    --n;
    recurse_n(n);

    // Your algorithm stuff here.
}

Это облегчит понимание того, что происходит.Хотя я бы добавил, что вы, возможно, захотите выполнить алгоритм перед вызовом recurse_n, но все зависит от того, что делает ваш алгоритм.

Если подумать, то, как я написалон будет повторяться до тех пор, пока n не станет меньше или равно 0, прежде чем выполнять какую-либо работу алгоритма.Возможно, вы захотите выполнить алгоритм, а затем выполнить повторение.

Answer 2

Прежде всего, используйте std :: vector и цикл (я предполагаю, что x (), y () и z () возвращают int s, которые вам нужны, вы также можете использовать вектор для хранениязначения):

void fill( std::vector<int> &vec, std::vector<int> &values )
{
    size_t nValues = values.size();
    size_t sz = vec.size();
    for( size_t i=0; i<sz; i=i+nValues )
    {
        for( size_t j=0; j<nValues; ++j )
        {
            vec[i] = values[j];
        }
    }
}

int main()
{
    std::vector<int> vec;
    std::vector<int> values;
    /* fill values vector here */
    vec.resize( 512 ); // (arbitraty) size you need
    fill( vec, values );

    return 0;
}

Это больше для C ++ и намного быстрее, чем рекурсивная функция.Также: сохраните значения x, y и z, чтобы соответствующий алгоритм выполнялся только один раз.

Answer 3

Я не думаю, что это жизнеспособный способ сделать это, поскольку: пусть T(n) обозначает время выполнения вашей функции (зависит от входного параметра n).

Базовый случай n=0 дает следующее время выполнения: T(0)=c, то есть некоторое постоянное время выполнения c.

Теперь вы можете определить рекурсивную формулу для времени выполнения, где n>0: T(n)=sum(i = 0 to n-1: T(i)).

Если вы решите это уравнение, вы получите это T(n)=O(2^n), что означает, что ваш алгоритм экспоненциальный, что означает, что он не поддается обработке на практике.

Answer 4

Рекурсия для заполнения массива является допустимым (даже лучшим) вариантом, если ваш алгоритм удовлетворяет следующим требованиям:

1. Значение в позиции n зависит от значений по крайней мере некоторых иззначения, которые были до него
2. Нет (известного) способа определить значение в позиции n без предварительного определения более ранних значений, от которых оно зависит.

Пример, которыйЭтим требованиям соответствуют числа Фибоначчи .Потому что вы не можете определить n-ое число без предварительного определения всех более ранних чисел (хотя существуют некоторые комбинации клавиш).

Примером, который не соответствует этим требованиям, является массив, заполненный квадратомindex, где значение в позиции n равно n^2.

Наконец, я бы посоветовал вам переписать вашу функцию в соответствии с шаблоном в ответе ДэйвДжонстона на ваш вопрос, если это возможно.

Answer 5

Джим Даниэль прав, рекурсия здесь - это излишество.Вы ничего не возвращаете из функции, и похоже, что вы используете только «n» для контроля количества рекурсий.Использование простого цикла for было бы намного понятнее и эффективнее.

Answer 6

Мне немного неясно по этому вопросу, но, похоже, у вас есть набор переменных a, b, c, ..., z, и вы хотите заполнить массив, чтобы он содержал a, b, c, ..., z, a, b, c, ..., z, a, .... Если это так, то, вероятно, проще всего поместить исходные переменные в их собственный однопроходный массив a, b, c, ..., z и memcpy в целевой массив, пока он не будет заполнен

#define NUM 3
int a, b, c; // source variables
void fill(int* arr, unsigned int size) {
    int src[] = {a, b, c};
    unsigned int i;
    for(i = 0; i < size / NUM; i++)
        memcpy(arr + (NUM * i), src, sizeof(int) * NUM);
    memcpy(arr + (NUM * i), src, sizeof(int) * (size % NUM));
}