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

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

В рекурсивной функции обязательно должно присутствовать хотя бы одно условие, при выполнении которого последовательность рекурсивных вызовов должна быть прекращена.

Классический пример рекурсивной функции – вычисление факториала числа.

#include <iostream>

using namespace std;

// Функция вычисления факториала - рекурсивная

unsigned long fact(unsigned int n){

if (n<1)

return 1;

else

return n*fact(n-1);

}

void main()

{

unsigned int n;

setlocale(LC_ALL, "Russian");

cout << "Введите неотицательное число: ";

cin >> n;

cout << "\nЕго факториал: " << fact(n) << '\n';

system("pause");

}

Если попытаться отследить по тексту программы процесс выполнения рекурсивной функции, то мы придем к такой ситуации: войдя в рекурсивную функцию, мы «движемся» по её тексту до тех пор, пока не встретим её вызова, после чего мы опять начнем выполнять ту же самую функцию с начала. При этом следует отметить самое важное свойство рекурсивной функции – её первый вызов ещё не закончился. При втором и последующих вызовах функции копируется её части, связанные с данными (формальные, фактические параметры, локальные переменные и точка возврата). Алгоритм (операторы, выражения) рекурсивной функции не меняется, поэтому он присутствует в памяти компьютера в единственном экземпляре.

Рассмотрим подробнее работу программы при n = 3.

При вызове любой функции её аргументы, автоматические локальные переменные и точка возврата помещаются в системный стек – специальную область памяти, используемую для вызова функций. При использовании рекурсивной функции количество её вызовов может быть велико и в стеке просто не останется памяти для выполнения очередного вызова. Эта ситуация называется переполнением стека и при большой глубине рекурсии она вполне вероятна.

При косвенной рекурсии осуществляется перекрёстный вызов функциями друг друга. Это один из случаев, когда объявление функции обязательно, т.к. её нельзя определить до первого использования.

Следует учитывать, что рекурсивные функции в общем случае работают медленнее обычных функций, выполняющих аналогичные действия итеративно. Это происходит из-за накладных расходов на вызовы функций и работу со стеком.