Рекурсивные функции в C / C ++

Question

Если мы рассмотрим рекурсивные функции в C / C ++, они полезны в любом случае? Где именно они используются в основном? Есть ли какие-либо преимущества с точки зрения памяти при использовании рекурсивных функций?

Редактировать: рекурсия лучше или использовать цикл while?

Answer 1

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

В большинстве случаев рекурсивные функции не экономят память по сравнению с итерационными решениями. Еще хуже то, что они потребляют стековую память, которая относительно скудна.

Answer 2

Рекурсия окончательно имеет преимущества при задачах с рекурсивной природой. Другие плакаты назвали некоторые из них.

Использование возможности C для рекурсии определенно имеет преимущества в управлении памятью. Когда вы пытаетесь избежать рекурсии, большую часть времени для решения проблемы используется собственный стек или другой динамический тип данных. Это включает в себя динамическое управление памятью в C / C ++. Динамическое управление памятью является дорогостоящим и подвержено ошибкам!

Вы не можете разбить стек

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

PS: также стек не фрагментируется, как это делает кучи памяти. Таким образом, можно также сэкономить память, используя стек / рекурсию.

Answer 3

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

Answer 4

Реализация QuickSort с использованием и без использования рекурсии, тогда вы сами можете определить, полезно это или нет.

Answer 5

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

unsigned greatest_common_divisor_iter(unsigned x, unsigned y)
{
    while (y != 0)
    {
        unsigned temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

unsigned greatest_common_divisor(unsigned x, unsigned y)
{
    return y == 0 ? x : greatest_common_divisor(y, x % y);
}

На мой вкус, в итерационной версии происходит слишком много переименований. В рекурсивной версии все неизменно, так что вы можете даже сделать x и y const, если хотите.

Answer 6

Стоит упомянуть одну вещь: в большинстве функциональных языков (например, Scheme) вы можете воспользоваться преимуществами оптимизации хвостовых вызовов и, таким образом, вы можете использовать рекурсивные функции без увеличения объема памяти в вашем стеке.

По сути, сложные рекурсивные хвостовые вызовы могут безупречно выполняться в Scheme, тогда как в C / C ++ те же самые вызовут переполнение стека.

Answer 7

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

Answer 8

При использовании рекурсии вы можете хранить данные в стеке (фактически, в контексте вызова всех функций над текущим экземпляром), которые вы вместо этого должны были бы хранить в куче с динамическим размещением, если пытались то же самое с while петлей. Подумайте о большинстве алгоритмов «разделяй и властвуй», в которых для каждого вызова нужно сделать две вещи (то есть один из вызовов не является рекурсивным).

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

Answer 9

Рекурсивные функции упрощают кодирование решений, имеющих рекуррентное отношение .

Например, факториальная функция имеет рекуррентное отношение:

 factorial(0) = 1
 factorial(n) = n * factorial(n-1)

Ниже Iреализовали факториал с использованием рекурсии и зацикливания.

Определенная выше рекурсивная версия и рекуррентное отношение выглядят аналогично и, следовательно, легче для чтения.

Рекурсивно:

double factorial ( int n )
{
 return ( n ? n * factorial ( n-1 ) : 1 );
}

Циклы

double factorial ( int n )
{
 double result = 1;
 while ( n > 1 )
 {
  result = result * n;
  n--;
 }
 return result;
}

Еще одна вещь:

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

Answer 10

Я вижу две причины использования рекурсии:

• алгоритм работает с рекурсивными структурами данных (например, с деревом)
• алгоритм имеет рекурсивный характер (часто случается для математических задач, поскольку рекурсия часто предлагает красивые решения)

Обращайтесь с рекурсией осторожно, так как всегда существует опасность бесконечной рекурсии.