Рекурсия
С++ позволяет определять рекурсивные функции, т.е. функции которые вызывают сами себя напрямую или опосредованно.
Например, следующая функция вычисляет факториал:
int factorial(int n)
{
if (n == 0) return 1;
return factorial(n — 1) * n;
}
Посмотрим на графике, что в этом случае произойдет:
допустим мы хотим посчитать факториал числа 3
factorial(3);
Все будет согласно данной картинке:
Факториал от 3 вызовет факториал от 2,
факториал от 2 вызовет факториал от 1,
факториал от 1 вызовет факториал от 0,
факториал от 0 вернет 1, которая подставится в return factorial (0)*1 ; //= 1*1=1 это значение factorial(1)
Посчитанное значение подставится в return factorial (1)*2; //=1*2 =2 это значение factorial(2)
Посчитанное значение подставится в return factorial (2)*3; //=2*3=6 это значение factorial(3)
Итог: факториал числа 3=6
Проверим 3!=3*2*1=6
Плюсы рекурсии:
- некоторые функции невозможно решить без рекурсии
- необязательно знать заранее число итераций
Минусы рекурсии:
- сложно прогнозировать требуемый объем памяти
- зачастую сложность понимания принципа ее работы и условия выхода.
Примечания:
Все рекурсивно вызываемые функции как правило располагаются друг за другом в памяти
ВСЕГДА нужно предусматривать условие выхода из рекурсии, иначе она будет бесконечной!