Рекурсивные функции в C++
Напоминание. Рекурсивной называется функция, которая вызывает саму себя. Такая рекурсия называется прямой. При косвенной рекурсии, две или более функций вызывают друг друга.
При рекурсивном вызове функции в стеке создается копия значений ее параметров, как и при вызове обычной функции, после чего управление передается первому исполняемому оператору функции.
При повторном вызове этот процесс повторяется. Ясно, что для завершения вычислений каждая рекурсивная функция должна содержать хотя бы одну нерекурсивную ветвь алгоритма, заканчивающуюся оператором возврата.
При завершении функции соответствующая часть стека освобождается, и управление передается вызывающей функции, выполнение которой продолжается с точки, следующей за рекурсивным вызовом.
Приведем пример рекурсивной функции, вычисляющей факториал.
To же самое можно записать короче:
}
При рекурсивном вызове функции в стеке создается копия значений ее параметров, как и при вызове обычной функции, после чего управление передается первому исполняемому оператору функции.
При повторном вызове этот процесс повторяется. Ясно, что для завершения вычислений каждая рекурсивная функция должна содержать хотя бы одну нерекурсивную ветвь алгоритма, заканчивающуюся оператором возврата.
При завершении функции соответствующая часть стека освобождается, и управление передается вызывающей функции, выполнение которой продолжается с точки, следующей за рекурсивным вызовом.
Приведем пример рекурсивной функции, вычисляющей факториал.
long fact(long n){
if (n==0 || n==1) return 1;
return (n * fact(n - 1);
}
long fact(long n){
return (n>1) ? n * fact(n - 1) : 1;
