Зачем нужна рекурсия в с
Рекурсивные функции — это функции, которые вызывают сами себя. Такие функции довольно часто используются для обхода различных представлений. Например, если нам надо найти определенный файл в папке, то мы сначала смотрим все файлы в этой папке, затем смотрим все ее подпак
Например, определим вычисление факториала в виде рекурсивной функции:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; auto result < factorial(n)>; std::cout unsigned long long factorial(unsigned n) < if(n >1) return n * factorial(n-1); return 1; >
В функции factorial задано условие, что если число n больше 1, то это число умножается на результат этой же функции, в которую в качестве параметра передается число n-1. То есть происходит рекурсивный спуск. И так далее, пока не дойдем того момента, когда значение параметра не будет равно 1. В этом случае функция возвратит 1.
Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1; .
Например, при вызове factorial(5) получится следующая цепь вызовов:
- 5 * factorial(4)
- 5 * 4 * factorial(3)
- 5 * 4 * 3 * factorial(2)
- 5 * 4 * 3 * 2 * factorial(1)
- 5 * 4 * 3 * 2 * 1
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:
#include unsigned long long fib(unsigned); int main() < for(unsigned i<>; i < 10; i++) < auto n = fib(i); std::cout std::cout unsigned long long fib(unsigned n)
Результат работы программы — вывод 10 чисел из последовательности Фиббоначчи на консоль:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
В примерах выше функция напрямую вызывала саму себя. Но рекурсивный вызов функции также может быть косвенным. Например, функция fun1() вызывает другую функцию fun2(), которая, в свою очередь, вызывает fun1(). В этом случае функции fun1() и fun2() также называются взаимно рекурсивными функциями.
Стоит отметить, что нередко рекурсивные функции можно представить в виде циклов. Например, для вычисления факториала вместо рекурсии используем цикл:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; std::cout unsigned long long factorial(unsigned n) < unsigned long long result; for(unsigned i; i return result; >
И нередко циклические конструкции более эффективны, чем рексурсия. Например, если функция вызывает себя тысячи раз, потребуется большой объем стековой памяти для хранения копий значений аргументов и адреса возврата для каждого вызова, что может привести к тому, что программа быстро исчерпает выделенную для нее память стека, поскольку объем памяти стека обычно фиксирован и ограничен. что может привести к аварийному завершению программы. Поэтому в таких случаях, как правило, лучше использовать альтернативные подходы, например цикл. Однако, несмотря на накладные расходы, использование рекурсии часто может значительно упростить написание программы.
Зачем использовать рекурсии в C#?
Только подобрался к использованию рекурсий, и практически сразу возник сабжевый вопрос. В видеокурсе и текстах, которые я успел изучить, плюсом использования рекурсии называется более сокращённая запись. При этом, например, факториал циклом описывается не сильно длиннее, и при этом запись гарантированно поймёт большая часть программистов, которые будут её читать. А чтобы понять рекурсию, надо сначала понять рекурсию. С другой стороны, замеры времени исполнения показали, что разницы в расчёте факториала (небольшого, правда) нет. А вот если описать сложение, скажем, коллекции целых чисел, то разница огромная, и не в пользу рекурсии. Я допускаю, что описываю криво, но пока ничего лучше родить не смог. Итак, есть класс SomeNums, реализующий IEnumerable(int); в нём есть список num, хранящий собственно множество. Вот цикл:
public int CycSum()
Вот рекурсия:
public int RecSum (int step)
И вот я где-нибудь в Main делаю так:
var n = new SomeNums(Enumerable.Range(1, 1000)); - Среднее время для рекурсии: 0,034 468
- Среднее время для цикла: 0,006 387
И, конечно, если я попробую увеличить количество членов множества, то получу переполнение стека.
Я понимаю, что использовать рекурсию так, как это делаю я — некорректно. Но есть ли корректные способы? В общем, есть ли смысл использования рекурсии в C#?
И да, я в курсе, что есть LINQ с его Aggregate, но пост не об этом.
Отслеживать
задан 31 окт 2016 в 3:10
1,287 9 9 серебряных знаков 21 21 бронзовый знак
Есть структуры данных, с которыми удобнее работать с помощью циклов (например массивы), а с иными удобнее использовать рекурсию. Например, для обхода дерева с однородными узлами удобно написать функцию, которая принимает узел, выполняет над ним вычисления, а затем вызывает саму себя для каждого потомка.
31 окт 2016 в 3:56
Вообще, вопрос о целесообразности применения рекурсии достаточно спорный, и четкие рекомендации о том где и когда ее следует применять в общем случае сформулировать сложно. Просто попробуйте применять ее для решения разных задач на этапе обучения, чтобы «набить руку». На практике, к решению о том что целесообразно использовать рекурсию может быть принято исходя из конкретных условий задачи.
31 окт 2016 в 3:56
Попробуйте сделать что-то циклами там, где рекурсия не оконечная. Ну, хотя бы самое простое — обойти дерево. Задача решаема, но уже даже в такой простой задаче можно замахаться писать без рекурсии. В то время как с ней будет легко и просто. Что до «понимать рекурсию». Дело вкуса — мне обычно легче написать что-то с рекурсией, чем без нее — там, понятно, где она применима 🙂
31 окт 2016 в 5:09
Интересно, что о деревьях я вообще не задумывался, когда писал вопрос. Это, конечно, моя вина, но если бы примеры с деревом (или вообще любые примеры, где рекурсия ОЧЕВИДНО лучше цикла) были в учебных материалах, понять было бы значительно проще.
31 окт 2016 в 5:25
@Uranus, оформите свой комментарий в виде ответа, пожалуйста
31 окт 2016 в 5:55
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Есть структуры данных, с которыми удобнее работать с помощью циклов (например массивы), а с иными удобнее использовать рекурсию. Например, для обхода дерева с однородными узлами удобно написать функцию, которая принимает узел, выполняет над ним вычисления, а затем вызывает саму себя для каждого потомка.
Кроме того, рекурсия нередко применяется в алгоритмах, там где результат вычисления зависит от результата той же функции вызванной с другими параметрами или там где сложно заранее задать число итераций. Например — quicksort. Даже математические формулы можно выразить с помощью рекуррентной формулы. Взять тот же факториал:
Это объясняет почему вычисление факториала так популярно в учебных материалах.
Кроме преимуществ, у рекурсии есть и известные недостатки. Одна из самых известных проблем упомянута в вопросе. При достижение слишком большой глубины рекурсии возникает переполнение стека, так как при вызове функции ее аргументы и адрес возврата помещаются в стек, размер которого конечен. Современные компиляторы умеют решать эту проблему, но для этого необходимо чтобы рекурсивная функция была реализована определенным образом. Так, если вызов самой себя является последней операцией функции, то компилятор сможет развернуть рекурсию в обычный цикл. Этот прием называется хвостовая рекурсия.
Вообще, вопрос о целесообразности применения рекурсии достаточно спорный, и четкие рекомендации о том где и когда ее следует применять в общем случае сформулировать сложно. Просто попробуйте применять ее для решения разных задач на этапе обучения, чтобы «набить руку». На практике, решение о том что целесообразно использовать рекурсию может быть принято исходя из конкретных условий задачи.
Зачем нужна рекурсия в с
Отдельно остановимся на рекурсивных функциях. Рекурсивная функция представляет такую конструкцию, при которой функция вызывает саму себя.
Рекурсивная функция факториала
Возьмем, к примеру, вычисление факториала, которое использует формулу n! = 1 * 2 * … * n . То есть по сути для нахождения факториала числа мы перемножаем все числа до этого числа. Например, факториал числа 4 равен 24 = 1 * 2 * 3 * 4 , а факторил числа 5 равен 120 = 1 * 2 * 3 * 4 * 5 .
Определим метод для нахождения факториала:
int Factorial(int n)
При создании рекурсивной функции в ней обязательно должен быть некоторый базовый вариант , с которого начинается вычисление функции. В случае с факториалом это факториал числа 1, который равен 1. Факториалы всех остальных положительных чисел будет начинаться с вычисления факториала числа 1, который равен 1.
На уровне языка программирования для возвращения базового варианта применяется оператор return :
if (n == 1) return 1;
То есть, если вводимое число равно 1, то возвращается 1
Другая особенность рекурсивных функций: все рекурсивные вызовы должны обращаться к подфункциям, которые в конце концов сходятся к базовому варианту:
return n * Factorial(n - 1);
Так, при передаче в функцию числа, которое не равно 1, при дальнейших рекурсивных вызовах подфункций в них будет передаваться каждый раз число, меньшее на единицу. И в конце концов мы дойдем до ситуации, когда число будет равно 1, и будет использован базовый вариант. Это так называемый рекурсивный спуск.
Используем эту функцию:
int Factorial(int n) < if (n == 1) return 1; return n * Factorial(n - 1); >int factorial4 = Factorial(4); // 24 int factorial5 = Factorial(5); // 120 int factorial6 = Factorial(6); // 720 Console.WriteLine($"Факториал числа 4 = "); Console.WriteLine($"Факториал числа 5 = "); Console.WriteLine($"Факториал числа 6 = ");
Рассмотрим поэтапно, что будет в случае вызова Factorial(4) .
-
Сначала идет проверка, равно ли число единице:
if (n == 1) return 1;
Но вначале n равно 4, поэтому это условие ложно, и соответственно выполняется код
return n * Factorial(n - 1);
То есть фактически мы имеем:
return 4 * Factorial(3);
Factorial(3)
Опять же n не равно 1, поэтому выполняется код
return n * Factorial(n - 1);
То есть фактически:
return 3 * Factorial(2);
Factorial(2)
Опять же n не равно 1, поэтому выполняется код
return n * Factorial(n - 1);
То есть фактически:
return 2 * Factorial(1);
Factorial(1)
Теперь n равно 1, поэтому выполняется код
if (n == 1) return 1;
В итоге выражение
Factorial(4)
В реальности выливается в
4 * 3 * 2 * Factorial(1)
Рекурсивная функция Фибоначчи
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фибоначчи. n-й член последовательности Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. То есть последовательность Фибоначчи будет выглядеть так 0 (0-й член), 1 (1-й член), 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . Для определения чисел этой последовательности определим следующий метод:
int Fibonachi(int n) < if (n == 0 || n == 1) return n; return Fibonachi(n - 1) + Fibonachi(n - 2); >int fib4 = Fibonachi(4); int fib5 = Fibonachi(5); int fib6 = Fibonachi(6); Console.WriteLine($"4 число Фибоначчи = "); Console.WriteLine($"5 число Фибоначчи = "); Console.WriteLine($"6 число Фибоначчи = ");
Здесь базовый вариант выглядит следующий образом:
if (n == 0 || n == 1) return n;
То есть, если мы ищем нулевой или первый элемент последовательности, то возвращается это же число — 0 или 1. Иначе возвращается результат выражения Fibonachi(n — 1) + Fibonachi(n — 2);
Рекурсии и циклы
Это простейшие пример рекурсивных функций, которые призваны дать понимание работы рекурсии. В то же время для обоих функций вместо рекурсий можно использовать циклические конструкции. И, как правило, альтернативы на основе циклов работают быстрее и более эффективны, чем рекурсия. Например, вычисление чисел Фибоначчи с помощью циклов:
static int Fibonachi2(int n) < int result = 0; int b = 1; int tmp; for (int i = 0; i < n; i++) < tmp = result; result = b; b += tmp; >return result; >
В то же время в некоторых ситуациях рекурсия предоставляет элегантное решение, например, при обходе различных древовидных представлений, к примеру, дерева каталогов и файлов.
О пользе рекурсии
Эту заметку о пользе рекурсии я написал после прочтения соответствующей части книги С. Макконнелла «Совершенный код». Книга прекрасная, но, на мой взгляд, автор совершенно напрасно обещает уволить сотрудника, использующего рекурсию. Мне рекурсия помогала много раз, и я видел множество превосходных примеров её использования.
В заметке я буду рассматривать рекурсию на классическом примере — вычисление факториала. На более сложных зачах эффект от использования рекурсии (как положительный, так и отрицательный) может оказаться на много больше.
Компактность записи
Итак, давайте сравним записи функций, вычисляющих факториал с использованием рекурсии и без использования рекурсии. Оказывается, слухи о громоздкости рекурсии во многом преувеличены.
Небольшое замечание: для краткости, все мои реализации (и рекурсивные и не рекурсивные) будут достаточно просты. Например, я не буду проверять корректность входных данных (отрицательное число, вообще не число). Вопросов надёжности кода я коснусь чуть ниже.
# пример 1 # вычисление факториала на языке Python без рекурсии def fac(n): f = 1 i = 2 while i Многие могут сказать, что функция чрезмерно усложнена добавлением переменной i . Чуть ниже, я поясню, зачем я это сделал, а пока приведу классический вариант:
# пример 2 # Python; без рекурсии; классика def fac(n): f = 1 while n > 1: f *= n n -= 1 return f У такого подхода есть один важный недостаток, к нему мы скоро вернёмся. А пока давайте посмотрим на рекурсивные реализации.
Сперва классическая реализация с рекурсией, всё на том же Python:
# пример 3 # Python; с рекурсией; классика def fac(n): if n == 0: return 1 else: return n * fac(n-1) Обратите внимание, на сколько близко эта запись перекликается с математическим определение факториала.
Можно сэкономить одну строчку:
# пример 4 (экономичная запись примера 3) # Python; с рекурсией; классика def fac(n): if n == 0: return 1 return n * fac(n-1) Ту же самую мысль можно записать ещё компактней
# пример 5 (одно-строчная запись примера 3) def fac(n): return (1 if n == 0 else n * fac(n-1)) Этот пример работает только в Python 2.5 и старше.
Приведу два примера на Haskell:
-- пример 7 -- запись примера 3 на Haskell fac n = if n == 0 then 1 else n * fac (n-1) Приведу ещё один, более компактный, но вполне понятный для неподготовленного читателя:
-- пример 8 -- реализация рекурсивного вычисления факториала -- на Haskell; дополнительно компактности удалось -- достичь за счёт использования клозов (от clause) fac 0 = 1 fac n = n * fac (n-1) Можно приводить ещё множество реализаций вычисления факториала, но мне кажется, что приведённых примеров достаточно, чтобы развеять миф о том, что рекурсивные реализации громоздки.
На мой взгляд, дело обстоит противоположным образом: в тех случаях, где рекурсия оправдана, она позволяет значительно сократить объём кода и сделать его на много понятней.
Как же можно повысить понятность кода, используя рекурсию?
Неизменяемость переменных
При программировании бывает полезно придерживаться концепции неизменяемости переменных (многие языки программирования вообще не допускают изменения переменных). Это позволяет убить сразу много зайцев:
- во-первых, вы избавляетесь от сайд-эффектов (side effect) — побочных эффектов, связанных с тем, что одна и та же переменная принимает разные значения в разные моменты времени;
- во-вторых, вы можете легко проверять данные на корректность; это достаточно делать один раз и все проверки можно группировать, скажем, в начале функции; это повышает не только надёжность кода, но и его читабельность, а так же, позволяет ничего не забыть;
- в-третьих, вы существенно повышаете читабельность кода, так как читающему не надо просматривать весь код, чтобы отследить эволюцию переменной; ему достаточно найти то место, где переменной присвоено значение, а дальше он может быть уверен, что это значение не изменится.
Давайте рассмотрим эти аспекты подробней.
Избавление от сайд-эффектов (side effect)
Рассмотрим рекурсивную и не рекурсивную реализацию. Повторю их здесь.
Не рекурсивная (одна из, она мне нравится больше; почему — поясню ниже)
# пример 1 # вычисление факториала на языке Python без рекурсии def fac(n): f = 1 i = 2 while i Тут мы видим сразу две изменяемые переменные — f и i . Причём i оказывает влияние на f в одном месте, а изменяет своё значение — в другом. Это потенциальный источник ошибок такого вида:
# пример 1 с ошибкой def fac(n): f = 1 i = 2 while i Даже в таком тривиальном коде заметить ошибку не легко. С увеличением объёма кода, находить ошибки, связанные с побочными эффектам, становится очень сложно.
Самое неприятное в таких ошибках то, что компилятор или интерпретатор, в большинстве случаев, ничего не заподозрит; с его точки зрения, код абсолютно правильный. Чтобы найти такую ошибку, вам придётся кропотливо вычитывать весь код (или не менее кропотливо работать в отладчике, или читать километровые файлы детальных протоколов, одно другого не слаще), следя за всеми изменениями переменных, отслеживая множество вариантов развития событий, учитывая возможную много-поточность выполнения операций. Весь этот ад появляется только потому, что переменные в нашей программе изменяемые и одно действие наводит побочный эффект на другое действие.
Вариант с рекурсией полностью избавлен от этого недостатка (приведу его здесь снова):
# пример 3 # Python; с рекурсией; классика def fac(n): if n == 0: return 1 else: return n * fac(n-1) В процессе выполнения функции fac ни одна переменная не изменяется. Это обстоятельство может сильно упростить чтение и понимание кода.
Неизменяемость переменных даёт ещё одно ценное преимущество: у каждой переменной появляется вполне определённое назначение, которое не может быть изменено.
Лёгкость проверки корректности значений
Так как значения не изменяются, их можно легко проверять на корректность. Причём все проверки можно группировать, не опасаясь, что переменная изменится к моменту, когда над ней будут производиться какие-то действия.
Строго говоря, проверка становится вполне естественной веткой в существующем алгоритме. Вот модифицированный пример 3:
# пример 3 с проверкой значений на "не-отрицательность" def fac(n): if n == 0: return 1 if n > 0: return n * fac(n-1) else: return 'ERROR' Чтобы реализовать аналогичную проверку в не рекурсивном варианте кода (примеры 1 и 2), пришлось бы добавить отдельный проверяющий механизм. И это не случайно, причины кроются в различном подходе к работе с данными. К этим различиям я ещё вернусь в секции «"Данные, управляемые программами" против "программ, управляемых данными"».
Однозначность назначения каждой переменной
Действительно, если переменные сохраняют свои значения, то и их назначение остаётся строго неизменным. В сочетании с удачными именами это обстоятельство может оказать неоценимую помощь при чтении и отладке кода.
Взгляните ещё раз на рекурсивный пример 3: переменная n сохраняет единственное назначение.
Чтобы идея была понятней, давайте введём ещё одну переменную (конечно же, она тоже будет неизменяемой):
# пример 3 с дополнительно переменной def fac(n): if n == 0: f = 1 else: f = n * fac(n-1) return f Теперь переменных две и их смысл одинаков везде, где они используются: n — аргумент, f — факториал n (и ни что иное).
Теперь пришло время объяснить, почему мне так не симпатичен пример 2 (приведу его здесь снова):
# пример 2 # Python; без рекурсии; классика def fac(n): f = 1 # первое использование f while n > 1: f *= n # второе использование f n -= 1 return f # третье использование f Здесь переменная f используется трижды, и все три раза она имеет разный смысл:
- первый раз — начальное значение — фиксированная константа;
- второй раз она используется как аккумулятор для хранения промежуточных результатов;
- трети раз — это искомое значение — факториал n.
Этот код — прекрасный образец того, как можно максимально эффективно запутывать программу, используя одну и ту же переменную в разных качествах.
Конечно, в данном случае, прочитать программу не сложно, но если она будет решать более сложную задачу, содержать тысячи строк, а переменная f будет не одна и будет не скаляром. Понять замысел программиста станет очень сложно.
И снова, источник всех бед только то, что переменная f — изменяемая.
«Данные, управляемые программами» против «программ, управляемых данными»
Существует два подхода к обработке данных, имеющих фундаментальные различия.
Первый — «программа управляет данными». Это наиболее простой и общеизвестный способ взаимодействия с данными. Если данные просты, то он позволяет без труда обрабатывать их, но если данные сложны (например, это некие конструкции, допускающие многократные вложения: HTML, XML, PostScript или просто программа на некотором языке высокого уровня), то алгоритму приходится обрабатывать множество возможных вариантов. Одна из наибольших проблем — обработка ошибок. Чтобы точно диагностировать ошибку, приходится рассматривать множество вариантов во множестве мест кода. Группировка проверок может значительно помочь программисту, но такой подход таит потенциальную опасность того, что значение изменится где-то между проверкой его корректности и его использованием.
Создавая такой код, очень легко что-то упустить и создать «дырку» — такой код, который будет работать непредусмотренным образом, если получит непредусмотренные автором данные. То есть злоумышленник сможет скомбинировать такие входные данные, которые заставят код работать не так, как задумывал автор.
Второй подход — «данные управляют программой». Этот подход используется в функциональных языках программирования и наиболее чисто реализован (на мой взгляд) в XSLT.
При написании кода в этом стиле, вы не создаёте алгоритм, вы не описываете последовательность действий. Вы пишете набор «формул», которые потом будут применяться к входным данным для получения результата. В момент написания вы не знаете в каком порядке будут выполняться инструкции, которые вы кодируете; потому, что вы не знаете, какие данные будет обрабатывать ваша программа. Но благодаря тому, что все ваши переменные являются неизменяемыми, вы можете не волноваться о порядке выполнения команд.
Давайте я приведу чуть-модифицированный вариант третьего примера:
# пример 3 (чуть модифицированный) def fac(n): if n == 0: return 1 if n != 0: return n * fac(n-1) Такая запись делает более очевидным тот факт, что функция fac не кодирует никакого алгоритма; она не определяет последовательность действий. В ней записано два утверждения:
если n равно нулю, то результат -- 1 если n не равно нуля, то результат -- выражение Эти строки можно выполнять в любом порядке. Для программиста не важно в каком порядке они будут отрабатываться. Он может отладить каждую ветку отдельно, а потом объединить их, не опасаясь сайд-эффектов. То, какая именно ветка будет работать, определятся входными данными. Поэтому подход и называется «данные управляют программой».
Подход, когда данные управляют программой даёт множество преимуществ, основными из которых являются: лёгкость понимания кода и простота написания обработчиков ложных данных, независимость одних частей кода от других. Но главное, такой подход не позволяет программисту создавать «дырки».
Рекурсия расточительна
«More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity.»
— W. A. Wulf
«We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.»
— C. A. R. Hoare
Это правда. Очень существенным недостатком рекурсии, является её расточительность.
Но думая о производительности, всегда следует помнить, что обычно, процедуры, вызываемые часто и принимающие на себя большую нагрузку, составляют не большую часть программы. Остальные части могут быть спроектированы, жертвуя производительностью в пользу облегчения сопровождения и модификации и повышения надёжности кода.
Приведу один пример. Допустим вы разрабатываете программу-архиватор. Понятно, что процедура архивирования должна работать максимально быстро, чтобы не заставлять пользователя ждать. Но так же ясно, что пользователь не будет генерировать тысячи кликов мышкой или нажатий клавиш в секунду, разрешение экрана, скорее всего, не превысит миллион на миллион пикселей, а объём параметров командной строки не будет измеряться мегабайтами. То есть, для части кода, отвечающей за интерфейс, производительность не так существенна.
С другой стороны, алгоритм архивирования вряд ли изменится, и если он написан хорошо, то его доработка и развитие не понадобится. Этого нельзя сказать об интерфейсе, здесь совершенству нет предела. В таком случае, код, описывающий интерфейс, должен быть понятным, простым и легко наращиваться.
Любая программа (и комплексы программ тоже) имеет не так уж много мест, в которых оптимизация действительно нужна. В большинстве же случаев, оптимизация не даёт выигрыша в производительности, но затрудняет дальнейшее развитие программы.
Учитывая это обстоятельство, можно достаточно смело говорить о том, что использование рекурсии противопоказано лишь в немногих случаях. А в большинстве случаев использование рекурсии вполне допустимо, и при разумном применении, рекурсия может сослужить хорошую службу.
Кроме того, не надо забывать про хвостовую рекурсию. Нашу рекурсивную процедуру вычисления факториала можно записать так:
def fac(n, a=None): if a is None: a = 1 if n < 2: return a return fac(n - 1, a * n) Мы мало что изменили. Фактически, мы просто поменяли порядок умножения. Но теперь мы получили вычисление факториала с хвостовой рекурсией.
Она характерна тем, что после рекурсивного вызова не выполняется никаких действий (наш предыдущий вариант таким свойством не обладал). В этом случае компилятор может превратить рекурсию в цикл. В gcc это сделает уже -O2 -оптимизация. То есть, мы получили рекурсию без дополнительных накладных расходов.
Конечно, далеко не всегда удаётся переформулировать рекурсию в виде концевой.
Итого
Рекурсия позволяет создавать код с неизменяемыми переменными, что
- делает код более читабельным,
- защищает от ошибок типа «действия выполнены в не верном порядке», «использована не-инициализированная переменная» и других аналогичных,
- облегчает организацию контроля корректности входных данных,
- позволяет читать код с любого места, не просматривая его весь, отслеживая все изменения переменной,
- облегчает отладку.
В некоторых случаях, рекурсия позволяет более ясно сформулировать идею алгоритма; например, это относится к алгоритму быстрой сортировки — quicksort — который рекурсивен по своей природе.
Но, конечно, использовать рекурсию следует разумно. Нужно учитывать то, что часто (не всегда) она ведёт к большим расходам стека и некоторому снижению производительности.
Кроме того, прибегая к рекурсии, надо понимать, какую выгоду вы можете от неё получить, и стремиться максимизировать выгоду и минимизировать вклад отрицательных качеств рекурсии.
В любом случае, существует множество языков, в которых рекурсия — единственное средство, для выполнения многих действий. К таким языкам относятся не только «экзотические» функциональные языки, такие как Haskell, но и средства более широкого применения: XSLT-процессоры, макро-процессор m4 (основа системы autoconf и многих систем конфигурирования), и другие средства. Такое «тяготение» к рекурсии — не следствие ограниченности этих языков; напротив, эти языки специально оптимизированы для использования рекурсии; они активно эксплуатируют факт неизменяемости переменных и способны выполнить множество оптимизаций, избавляя программиста от многих забот.