В языке С функция может вызывать сама себя. В этом случае такая функция называется рекурсивной. Рекурсия — это процесс определения чего-либо на основе самого себя, из-за чего рекурсию еще называют рекурсивным определением.
Простым примером рекурсивной функции является factr(), которая вычисляет факториал целого неотрицательного числа. Факториалом числа n (обозначается n!) называется произведение всех целых чисел, от 1 до n включительно (для 0, по определению, факториал равен 1.). Например, 3! — это 1×2×3, или 6. Здесь показаны factr() и эквивалентная ей функция, в которой используется итерация:
/* рекурсивная функция */
int factr(int n) {
int answer;
if(n==1) return(1);
answer = factr(n-1)*n; /* рекурсивный вызов */
return(answer);
}
/* неркурсивная функция */
int fact(int n) {
int t, answer;
answer = 1;
for(t=1; t<=n; t++)
answer=answer*(t);
return(answer);
}
Нерекурсивное вычисление факториала, то есть вычисление с помощью fact(), выполняется достаточно просто. В этой функции в теле цикла, выполняющемся для t от 1 до n, вычисленное ранее произведение последовательно умножается на каждое из этих чисел. (Значение факториала для 0 получается, конечно, с помощью оператора присваивания. Значение факториала для 1 также получается умножением не на ранее полученное произведение, а на заранее подготовленное число, тоже равное 1.)
Работа же рекурсивной функции factr() чуть более сложная. Когда factr() вызывается с аргументом 0, то она сразу возвращает 1. Если же аргумент больше 0, то возвращается произведение factr(n-1)*n. Чтобы вычислить значение этого выражения, factr() вызывается с аргументом n-1. Это выполняется до тех пор, пока n не станет равным 0. Когда это произойдет, вызовы функции начнут возвращать вычисленные ими значения факториалов.
При вычислении 2! первый вызов factr() влечет за собой второй, теперь уже рекурсивный вызов с аргументом 1, который, в свою очередь, влечет третий, тоже рекурсивный вызов с аргументом 0. Этот вызов возвращает число 1, которое затем умножается на 1, а потом на 2 (первоначальное значение n). Ответ в данном случае равен 2. Попробуйте самостоятельно вычислить 3!. (Вам, возможно, захочется вставить в функцию factr() выражения printf(), чтобы видеть уровень каждого вывода, и то, какие будут промежуточные ответы.)
Когда функция вызывает сама себя, новый набор локальных переменных и параметров размещается в памяти в стеке, а код функции выполняется с самого своего начала, причем используются именно эти новые переменные. При рекурсивном вызове функции новая копия ее кода не создается. Новыми являются только значения, которые использует данная функция. При каждом возвращении из рекурсивного вызова старые локальные переменные и параметры извлекаются из стека, и сразу за рекурсивным вызовом возобновляется работа функции. При использовании рекурсивных функций стек работает подобно "телескопической" трубе, выдвигающейся вперед и складывающейся обратно.
Хотя и кажется, что рекурсия предлагает более высокую эффективность, но на самом деле такое бывает достаточно редко. Использование рекурсии в программах зачастую не очень сильно уменьшают их размер кода и обычно только незначительно увеличивает эффективность использования памяти. Кроме того, рекурсивные версии большинства программ могут выполняться несколько медленнее, чем их итеративные варианты, потому что при рекурсивных вызовах функций расходуются дополнительные ресурсы. Кроме того, большое количество рекурсивных вызовов функции может вызвать переполнение стека. Из-за того, что память для параметров функции и локальных переменных находится в стеке и при каждом новом вызове создается еще один набор этих переменных, то для переменных места в стеке может рано или поздно не хватить. Переполнение стека — вот обычная причина аварийного завершения программы, когда функция утрачивает контроль над рекурсивными обращениями.
Главным преимуществом рекурсивных функций является то, что с их помощью упрощается реализация некоторых алгоритмов, а программа становится понятнее. Например, алгоритм быстрой сортировки (описанный в части IV) трудно реализовать итеративным способом. Кроме того, для некоторых проблем, особенно связанных с искусственным интеллектом, больше подходят рекурсивные решения. И наконец, некоторым людям легче думать рекурсивными категориями, чем итеративными.
В тексте рекурсивной функции обязательно должен быть выполнен условный оператор, например if, который при определенных условиях вызовет завершение функции, т.е. возврат, а не выполнит очередной рекурсивный вызов. Если такого оператора нет, то после вызова функция никогда не сможет завершить работы. Распространенной ошибкой при написании рекурсивных функций как раз и является отсутствие в них условного оператора. При создании программ не отказывайтесь от функции printf(); тогда вы сможете увидеть, что происходит на самом деле и сможете прервать выполнение, когда обнаружите ошибку.