Рекурсивные алгоритмы

Рекурсия — процесс определения либо выражения функции, при котором ее значение для произвольных значений аргументов выражается известным образом через значения функции для меньших значений аргументов.

Функция f, для которой существует алгоритм оценки f(x) для любого x в области определения f, называется вычислимой.

Функция, для которой существует эффективная процедура ее вычисления на основе рекурсии, называется рекурсивной.

Пример: вычисление факториала числа используя рекурсию. Факториал числа выражается через рекурсивное соотношение n! = n · (n - 1)! и соотношение 1! = 1. Эти соотношения можно записать через функцию f(n) = n! как f(n) = n · f(n - 1) и f(1) = 1.

// Вычисление факториала с использованием рекурсивной функции
#include <iostream.h>

int f(int n)             // Рекурсивная функция
{
  if (n == 1)
    return 1;            // f(n) = 1
  else
    return n * f(n - 1); // f(n) = n f(n - 1)
}

main()                   // Главная функция
{
  int n;
  cout << "Введите n: ";
  cin >> n;
  cout << "n! = " << f(n) << endl;
  return 0;
}

Рекурсивно заданная функция может выражаться через несколько предыдущих значений.

Пример: числа Фибоначчи. В следующем примере рассмотрим последовательность чисел Фибоначчи. Последовательность определяется следующим образом: f(1) = 0, f(2) = 1, f(n) = f(n - 1) + f(n - 2).

int f(int n)                    // Рекурентная функция
{
  if (n == 0 || n == 1)
    return n;                   // f(0) = 0, f(1) = 1
  else
    return f(n - 1) + f(n - 2); // f(n) = f(n - 1) + f(n - 2)
}

Отметим, что данный алгоритм на каждом шаге рекурсии удваивает число вызовов функции. Таким образом, при вычислении числа Фибоначчи с номером n вызовов функции будет 2ⁿ. Такие алгоритмы называются алгоритмами с экспоненциальной сложностью. Они требуют больших вычислительных затрат и их нужно избегать.

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