Насколько далеко выполняется рекурсия в вашей функции в C ++?

Question

Я написал рекурсивные функции под руководством друга, который преподает мне C ++ (в качестве первого языка) Однако я не очень понимаю, что происходит. Он помог мне (и сообществу SO) написать функцию сортировки слиянием.

std::vector<int> mergeSort(std::vector<int> original)

//code here to create two vectors, farray and sarray, out of the 
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int

farray = mergeSort(farray);
sarray = mergeSort(sarray);

//code here merges the two into a single, final sorted std::vector   

В этой функции я назначаю:

farray = mergeSort(farray);
sarray = mergeSort(sarray);

Что именно здесь происходит? Он вызывает mergeSort с farray и sarray в качестве параметров и изменяет значение. Как далеко выполняется слияние mergeSort с самим собой? Просто до рекурсивного вызова функции?

Answer 1

Каждый раз, когда вы вызываете функцию рекурсивно, она эффективно создает новую копию необходимой информации и продолжает работу.

У вас может быть программа, которая повторяется «бесконечно», т. Е. До тех пор, пока у нее не закончатся ресурсы, обычно это место в стеке - пространство, в котором находятся эти копии. Это будет выглядеть как

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

Очевидно, что это не очень полезно, поэтому вы хотите написать программу, которая имеет ограничение по частоте повторения. Вот действительно простая программа, которая управляет этим:

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

Если вы скомпилируете и запустите это, скажите:

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

Вы получите результаты:

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $ 

Посмотрите, как его вызывают для 10, затем 9 и так далее, а затем, когда он достигает дна, он показывает, что возвращается на 1, затем 2 и так далее до 10?

Основное правило состоит в том, что каждая рекурсивная функция должна иметь нечто, составляющее базовый случай, то, которое действительно вызывает снова. В этом случае базовый случай равен count == 0, и на самом деле мы могли бы написать это как рекурсивное определение

recursome:
если c = 0: напечатать дно
если c> 0: счетчик печати и рекурсивный (c-1)

По мере продвижения по математике вы увидите много рекурсивных определений такого рода.

Вот несколько более изящная версия C с лучшим выводом:

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

Выход:

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10

Answer 2

Рекурсию можно понимать как практическое применение принципа индукции. Чтобы доказать утверждение P (n) для всех n, где P (n) означает «Сумма целых чисел от 1 до n равна n (n + 1) / 2», нам нужно доказать две вещи:

1. Базовый случай: P (n) выполняется для определенного целого числа. P (1) верно, потому что 1 = 1 (1 + 1) /2.
2. Индуктивный случай: Если P (n) истинно, тогда P (n + 1) должно быть истинно. 1 + ... + n + (n + 1) = n (n + 1) / 2 + (n + 1) = n (n + 1) / 2 + 2 (n + 1) / 2 = (n + 1) ((n + 1) +1) / 2, что является уставом P (n + 1).

Аналогично, в рекурсивной функции, такой как mergeSort, нам нужно обработать два случая:

1. Базовый случай: Если массив имеет один элемент, он сортируется; в противном случае
2. Рекурсивный регистр: Разделите массив на два меньших массива, объедините каждый из них в сортировку и объедините их.

Ключ в том, что эти два массива на меньше , чем оригинал, иначе один из них никогда не попадет в базовый вариант. Поскольку массивы разделены примерно пополам, глубина рекурсии в этом случае будет около log2 (n).

Что касается кода в вопросе, есть три вопроса:

1. Базовый корпус отсутствует.
2. Повторное использование переменных farray и sarray не является строго необходимым и может привести к путанице.
3. Код будет очень медленным из-за количества создаваемых и уничтожаемых std :: vectors. Лучший интерфейс для mergeSort принимает два вектора: итераторы в качестве входных данных, аналогично функции std :: sort ().

Новые программисты должны попробовать выполнить сортировку слиянием с бумагой и карандашом.

Answer 3

Проверьте это в словаре:

рекурсия : существительное. см рекурсия

Теперь, будучи серьезным, в приведенной выше шутке определение рекурсии дается в терминах самой рекурсии. Это рекурсия.

Рекурсивный алгоритм - это алгоритм, реализация которого основана на самом алгоритме. Процесс разработки такого алгоритма начинается с самого простого случая, решение которого либо известно заранее, либо может быть тривиально вычислено. Затем вы определяете алгоритм в терминах самого себя.

В качестве простого примера, вычисление n-й степени заданного целого числа i может быть функцией power( int number, int power ). Как вы могли бы это реализовать? во многих отношениях. Простейшим является вызов библиотеки, за которым следует цикл, или вы можете определить функцию в терминах самой себя:

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

Мы определили функцию в терминах самой себя. Вы начинаете с самого простого случая (n ^ 0 = 1). Если мы не в простейшем случае, вы можете выразить свой алгоритм через себя.

Программа запускается в основном с вызова power( 2, 10 ), который вызовет рекурсию и вызовет power( 2, 9 ), уменьшая проблему до меньшей проблемы, и затем будет составлять окончательный ответ с точки зрения более простой задачи.

Актуальная трассировка вызова будет:

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

При разработке рекурсивных алгоритмов это обычно помогало мне поверить в то, что алгоритм уже запущен и работает, и я просто работаю над уменьшением / компоновкой нового результата.

Answer 4

Загляните на страницу википедии для сортировка слиянием для получения дополнительной информации о том, что вы пытаетесь сделать.

Знайте, что вы делаете копию каждого вектора, заданного вами в качестве параметра. Вместо него используйте vector <> const &.

Answer 5

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

В вашем случае, если вы разделите переданный вектор и в итоге получите два вектора, каждый из которых содержит только 1 элемент, имеет ли смысл вызывать для них mergeSort ()? №

Вы можете справиться с этим, проверив размер farray и sarray и решив, вызывать ли mergeSort () для одного или обоих, прежде чем объединять их и возвращать комбинацию.

Что если у одного есть 2 предмета, а у одного - 1? Вызовите метод mergeSort () для размера 2, но не для размера 1.

Когда вызов mergeSort () не вызывает mergeSort () ни на farray, ни на sarray перед возвратом, рекурсия начнет раскручиваться.