Рекурсивные вызовы функции

Рекурсией называют способ организации подпрограммы, при котором она прямо или косвенно вызывает сама себя. Соответственно различают прямую и косвенную рекурсию.

При прямой рекурсии подпрограмма вызывает себя из своего раздела операторов. Схематично это можно представить на рисунке 7.1.

При косвенной рекурсии подпрограмма вызывает подпрограмму, которая прямо или косвенно вызывает первую. Схематично это можно представить на рисунке 7.2.

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

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

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

n! = 1 при n=0;

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

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

long fakt(int n)

{

return ((n==1)? 1: n*fakt(n-1));

}

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

Не нашли, что искали? Воспользуйтесь поиском: