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

Пример программы с рекурсивной функцией, которая вычисляет n-число Фибоначчи. Последовательность чисел Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2, n >= 2

В пределе отношение Fn / Fn-1 стремится к значению 1.618033… Это значение называется золотым сеченим или божественной пропорцией. Принято считать, что объекты, содержащие в себе золотое сечение, воспринимаются людьми как наиболее гармоничные.

#include <iostream.h>
#include <conio.h>

//Рекурсивная функция вычисления n-го числа Фибоначчи
int fib(int n)
{
  if (n == 0 || n == 1) //ветвь выхода из рекурсии
  {
    return n;
  }
  return fib(n-1) + fib(n-2); //рекурсивный вызов
}

void main()
{
  int n;
  cout « "n? ";
  cin » n;
  cout « "fib = " « fib(n);
  cout « "f = " « fib(n);
  getch(); 
}

Любую рекурсивную функцию можно заменить нерекурсивным вариантом. Нерекурсивный вариант функции вычисления числа Фибоначчи может быть таким:

int fib(int n)
{
  int fnew, fold, foldold; //3 последовательных числа Фибоначчи
  if (n == 0 || n == 1) return n;
  foldold = 0; fold = 1;
  for (int i = 2; i <= n; ++i)
  {
    fnew = fold + foldold;
    foldold = fold;
    fold = fnew;
  }
  return fnew;
}

Недостатки рекурсивных функций:

1. Увеличение памяти на повторные вызовы функции и многократное размещение в стеке формальных параметров и локальных переменных рекурсивной функции
2. Расход времени на многократное выполнение команд вызова функции
3. Переполнение стека программы, при большом количестве рекурсивных вызовов