Рекурсия

Любая функция в программе на языке С++ может быть вызвана рекурсивно, т.е. она может вызывать саму себя. Компилятор допускает любое число рекурсивных вызовов. При каждом вызове для формальных параметров и переменных с классом памяти auto и register выделяется новая область памяти, так что их значения из предыдущих вызовов не теряются, но в каждый момент времени доступны только значения текущего вызова.

Переменные, объявленные с классом памяти static, не требуют выделения новой области памяти при каждом рекурсивном вызове функции и их значения доступны в течение всего времени выполнения программы.

Классический пример рекурсии - это математическое определение факториала n!:

n! = 1 при n=0; n*(n-1)! при n>1.

Функция, вычисляющая факториал, будет иметь следующий вид:

long fakt(int n) { return ((n==1)? 1: n*fakt(n-1)); }

Хотя компилятор языка С++ не ограничивает число рекурсивных вызовов функций, это число ограничивается ресурсом памяти компьютера и при слишком большом числе рекурсивных вызовов может произойти переполнение стека.