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

Однако, следует понимать что рекурсия в математике и рекурсия в программировании далеко не одно и тоже. Как отметил Ален И. Голуб в книге «Веревка достаточной длины, чтобы… выстрелить себе в ногу» (п. 6. Если вы не можете сказать это по‑английски, то вы не сможете выполнить это и на Си/Си++) — математическое мышление может помешать писать хорошие программы. И как раз рекурсия наглядно демонстрирует эту мысль.

Математика абстрактна — в ней рекурсия работает в рамках математической логики, а это скорее логика вида «что было бы, если бы функция вызывала сама себя» — реальных вызовов функцией самой себя там нет — математики не вычисляют рекурсии пошагово (как это делает компьютер) поэтому там нет и описанных ниже побочных эффектов появляющихся у рекурсии в программировании. В математике рекурсия более универсальна чем цикл, но в программировании всё наоборот — здесь цикл намного гибче и универсальнее.

Негативные эффекты от рекурсии в программировании носят алгоритмический характер поэтому компиляторы языков программирования общего назначения не могут оптимизировать рекурсию — она неуправляема даже для программиста, не то что для компилятора. Компиляторы функциональных языков программирования умеют преобразовывать так называемую «хвостовую» рекурсию в цикл, убирая её негативные эффекты. Но «хвостовая» рекурсия позволяет реализовать лишь простейшие варианты рекурсии. В общем случае рекурсия эквивалентна нескольким псевдоциклам и анализ количества и функционала этих псевдоциклов нетривиален, а потому не подлежит оптимизации компилятором. По сути «хвостовая» рекурсия не более чем «заплатка» позволяющая вернуть в функциональные языки программирования опрометчиво удалённые из них циклы. Вред от мышления рекурсиями в программировании будет рассмотрен ниже на конкретных примерах.

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

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

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

Да, рекурсии в программировании обычно выглядят лаконично и математически красиво, что создаёт иллюзию — «здесь всё понятно», но н�� самом деле:

  • чаще всего под лаконичной записью скрывается весьма навороченный алгоритм;

  • реальная сложность рекуррентного алгоритма обычно далеко не очевидна из лаконичной записи самой рекурсии, именно поэтому программа с рекурсией очень плохо читаема;

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

Вычисление факториала

Вычисление факториала часто приводится в учебниках как простейший пример программирования рекурсии. Рассмотрим три варианта:

Код 1.1. Факториал через цикл while:

unsigned long long factorial(unsigned n) 
{
    if (n == 0) return 1;
    unsigned long long result = n;
    while (--n > 1)
        result *= n;
    return result;
};

Код 1.2. Факториал через рекурсию:

unsigned long long factorial_rec(unsigned n)
{
    if (n == 0) return 1;
    return n * factorial_rec(n - 1);
};

Код 1.3. Эквивалент алгоритма рекурсии через циклы:

unsigned long long factorial_eq(unsigned n)
{
    std::stack<unsigned> st;
    // цикл прямого хода рекурсии
    while (n != 0)
    {
        st.push(n);
        --n;
    }
    n = 1;
    // цикл обратного хода рекурсии
    while (!st.empty())
    {
        n *= st.top();
        st.pop();
    }
    return n;
}

Код 1.1 - логично и наглядно вычисляет факториал по формуле n⋅(n - 1)⋅(n - 2)⋅... ⋅3⋅2, здесь действительно всё просто и понятно.
Код 1.2 - рекурсия выглядит лаконично и симпатично, однако при запуске ведёт себя как код 1.3.
Код 1.3 - полагаю, никто в здравом уме не станет писать такое вместо кода 1.1. Здесь очевидно, что нет никакого смысла сначала в цикле запоминать в стеке значения n-1, n-2, n-3, ... чтобы потом в следующем цикле их оттуда доставать и перемножать, вместо того чтобы сразу их перемножить.

Рекурсия захламляет стек не только последовательностью n-1, n-2, n-3, ..., а ещё и адресом возврата из функции, но здесь и далее разбор этих "накладных расходов" опущен, поскольку рекурсия здесь рассматривается с точки зрения алгоритмической эффективности.

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

Код 1.4. Визуализация встроенных в рекурсию псевдоциклов:
unsigned long long factorial_rec(unsigned n)
{
    if (n == 0) return 1;
    std::println("n = {} - прямой ход", n);
    unsigned long long result = n * factorial_rec(n - 1);
    std::println("{}! = {} - обратный ход", n, result);
    return result;
};
результат для factorial_rec(8):
n = 8 - прямой ход
n = 7 - прямой ход
n = 6 - прямой ход
n = 5 - прямой ход
n = 4 - прямой ход
n = 3 - прямой ход
n = 2 - прямой ход
n = 1 - прямой ход
1! = 1 - обратный ход
2! = 2 - обратный ход
3! = 6 - обратный ход
4! = 24 - обратный ход
5! = 120 - обратный ход
6! = 720 - обратный ход
7! = 5040 - обратный ход
8! = 40320 - обратный ход

Здесь наглядно видно результат работы обоих псевдоциклов. Увидеть эти циклы можно и при пошаговой отладке программы. Но в программе с рекурсией (код 1.2) мы не видим никаких циклов, а значит у программиста нет возможности выкинуть лишний цикл. Это иллюстрация того что рекурсия неуправляема и плохо читаема (красивый лаконичный код рекурсии не соответствует реальному поведению программы и надо разбираться что там подразумевается между строк).

Вопрос на засыпку – тот кто посчитал пример рекуррентного вычисления факториала «простым и понятным» действительно с первого взгляда представил его в виде этой пары псевдоциклов и также с первого взгляда определил что этих псевдоциклов именно два (а не больше) или он просто попался в ловушку, залюбовавшись блеском вершины айсберга?
Не торопитесь отвечать на этот вопрос – подождите до разбора вычисления чисел Фибоначчи и функции Аккермана в следующей статье.

Здесь мы увидели что рекурсия ведёт себя как два псевдоцикла (в общем случае их может быть гораздо больше). Приставка "псевдо" уместна тут по следующим причинам:

  • эти циклы не прописаны в коде рекурсии явно, об их существовании и количестве приходится догадываться "читая между строк";

  • на уровне ассемблера циклы формируются командами условных или безусловных переходов, а псевдоциклы рекурсии командами call и ret;

  • псевдоциклы часто ведут себя очень похоже на циклы, но в некоторых случаях превращаются в особые конструкции, которые не имеют прямого аналога в формате цикла (см. ниже анализ кода 2.7).

Возведение в натуральную степень pow(x, n)

Бьярн Страуструп в книге "Язык программирования С++" (второе издание, раздел: 1.3.5. Функции) в качестве примера рекурсии предлагает функцию возведения действительного числа в целую положительную степень. Несложно доработать её до возведения в любую целую степень, но пока не будем загромождать пример и сделаем это позже (в коде 2.5).

Код 2.1. Возведение в натуральную степень через цикл без оптимизации:

double pow(float x, unsigned n)
{
      double result = 1.0;
      while (0 < n--)
            result *= x;
      return result;
}

В этом цикле временная переменная result последовательно умножается на x и делается это n раз. В итоге имеем result = x⋅x⋅x⋅…⋅x.

Код 2.2. Рекурсия от Бьярна Страуструпа по задумке должна делать тоже самое:

double pow(float x, unsigned n)
{
      switch (n)
      {
            case 0:  return 1.0;
            case 1:  return x;
            default: return x * pow(x, n - 1);
      };
};

Здесь, как и в случае с факториалом, наглядность программы резко снизилась и для того чтобы понять что здесь происходит придётся лезть в пошаговый отладчик и/или добавлять вывод отладочной информации. Лично мне чтобы понять как это работает и написать эквивалентный код потребовались и отладочный вывод и пошаговый разбор в отладчике и всё равно это оказалось не просто, потому что много нюансов. Рекурсия использует стек процессора в который сохраняет разнородную информацию. В C++ объекты стека типизированы, поэтому при написании эквивалента придётся либо использовать два объекта std::stack, либо сохранять в стек структуру.

Код 2.3. Алгоритмический эквивалент рекурсии:

double pow_eq(float x, unsigned n)
{
	struct stack_item {
		float x;
		unsigned n;
	};

	std::stack <stack_item> st;
	
	// цикл прямого хода
	while (true)
	{
		if (n == 0)
			return 1.0;
		if (n == 1) {
			st.push({ x, n });
			break;
		}
		st.push({ x, n-- });
	}
	double result = 1.0;
	// цикл обратного хода
	while (!st.empty())
	{
		x *= st.top().x;
		st.pop();
	}
	return x;
};
Код 2.4. Версии кода 2.2. и 2.3 с выводом отладочной информации.
double pow_rec(float x, unsigned n)
{
	double result;
	std::println("pow({}, {}) - прямой ход", x, n);
	switch (n)
	{
		case 0: return 1.0;
		case 1: result = x;
			break;
		default: result = x * pow_rec(x, n - 1);
	};
	std::println("pow({}, {}) = {} - обратный ход", x, n, result);
	return result;
};
//------------------------------------------------------------------
// 2.3 эквивалент рекурсии + отладочная информация
double pow_eq(float x, unsigned n)
{
	struct stack_item {
		float x;
		unsigned n;
	};

	std::stack <stack_item> st;

	// цикл прямого хода
	while (true)
	{
		std::println("pow({}, {}) - прямой ход", x, n);
		if (n == 0)
			return 1.0;
		if (n == 1) {
			st.push({ x, n });
			break;
		}
		st.push({ x, n-- });
	}
	double result = 1;
	// цикл обратного хода
	while (!st.empty())
	{
		result *= st.top().x;
		std::println("pow({}, {}) = {} - обратный ход", 
							st.top().x, st.top().n, result);
		st.pop();
	}
	return x;
};

Видим что:

  • цикл прямого хода просто запоминает в стеке значения x и n;

  • в цикле обратного хода, используется только извлечённый из стека x хотя все его извлечённые из стека значения одинаковы и соответственно не было никакого смысла забивать ими стек;

  • текущие значения n в стеке меняются от n до 1, но они не используются в цикле обратного хода;

  • в цикле прямого хода n используется как счётчик, и нет никакого смысла сохранять его в стек;

  • в цикле обратного хода в роли счётчика выступают занесённые в стек адреса возврата из функции, что в эквивалентном коде заменено на условие !st.empty();

  • сравнение с нулём, которое необходимо только для исключительного случая n == 0 осталось внутри цикла прямого хода и выполняется на каждой итерации.

Вывод: здравомыслящий программист не станет писать громоздкий и нелогичный код 2.3 вместо простого и наглядного кода 2.1, но именно код 2.3 является наглядной демонстрацией алгоритма работы "простого и красивого" рекуррентного кода 2.2.

Оптимизация pow

Последовательно n раз умножать result на x выглядит совершенно не серьёзно. Легко заметить что, при n = 2^k (где k натуральное число) можно цикл умножений заменить на цикл возведений в квадрат и этим многократно сократить количество умножений. Например, x^{16} можно вычислить так:x⋅x=x^2 => x^2⋅x^2 = x^4 => x^4⋅x^4 = x^8 => x^8⋅x^8=x^{16}, обойдясь 4 умножениями вместо 16. Но как быть когда n ≠ 2^k? Всё очень просто - любое натуральное число можно представить как сумму чисел 2^k, например, 27=16+8+2+1 =>x^{27} = x^{16}⋅x^8⋅x^2⋅x. Более того, двоичное представление чисел в компьютере уже является как раз таким представлением, например, десятичное число 11 в двоичном виде 0b1011, где 1 в нулевом, первом и третьем битах означают 2^3+2^1+2^0 = 8+2+1 = 11, а 0 во втором бите означает что 2^2 в этой сумме нет (отсчёт битов начинается с нулевого бита, поэтому второй бит в 0b1011 визуально находится на третьей позиции). Превращаем эту логику в код:

Код 2.5. Оптимизация возведения в целую степень:

// Быстрое возведение в натуральную степень
double pow(float x, unsigned n)
{
	double result = 1.0, tmp = x;
	while (n != 0)
	{
		if (n & 1)
			result *= tmp;
		tmp *= tmp;
		n >>= 1;
	};
	return result;
};

// И, наконец, добавим быстрое возведение в целую степень
// здесь return pow(...) не рекурсия, а вызов перегруженной функции
double pow(float x, int n)
{
	if (n < 0)
		return 1.0 / pow(x, static_cast<unsigned>(-n));
	return pow(x, static_cast<unsigned>(n));
};

Здесь tmp *= tmp; отвечает за последовательное возведение в квадрат, а if (n & 1) result *= tmp; и n >>= 1; на основе двоичного представления n определяют какие из x^{2k} попадут в результат, а какие следует пропустить, ограничившись возведением в квадрат для следующей итерации. В итоге, если n имеет тип uint_32t, то нам потребуется не более 64 умножений для pow(x, n). Огромная экономия по сравнению с максимально возможными 4'294'967'295 умножений без этой оптимизации!

А можно ли сделать подобную оптимизацию на основе рекурсии?
Да, переписать код 2.5 в формат рекурсии не сложно.

Код 2.6. Оптимизированное возведение в натуральную степень на основе рекурсии:

double pow_fast_rec(float x, unsigned n)
{
	if (n == 0) return 1.0; 
	if (n & 1)
		return = x * pow_fast_rec(x * x, n >> 1);
	return = pow_fast_rec(x * x, n >> 1);
};

А можно ли прийти к этому коду изначально опираясь на логику рекурсии?
Да, можно и так - один из вариантов описан здесь. Однако с логикой там всё мутно и сложно - много букв и формул, а в конструкции (n-1)/2 усматривается сакральный смысл по преобразованию нечётных чисел в чётные, хотя на самом деле вычитание единицы из нечётного числа обнуляет младший двоичный разряд, а целочисленное деление на два этот младший разряд отбрасывает независимо от того был он предварительно обнулён вычитанием единицы или нет.

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

Но вернёмся к анализу того что происходит в рекуррентной версии оптимизированной pow().

Код 2.7. Добавим вывод отладочной информации:
double pow_fast_rec(float x, unsigned n)
{
	double result;
	std::println("pow({}, {}) - прямой ход", x, n);
	if (n == 0) return 1.0; 
	if (n & 1)
		result = x * pow_fast_rec(x * x, n >> 1);
	else
		result = pow_fast_rec(x * x, n >> 1);
	std::println("pow({}, {}) = {} - обратный ход", x, n, result);
	return result;
};
Результат для pow_fast_rec(3, 120) с отладочной информацией:

pow(3, 120) - прямой ход pow(9, 60) - прямой ход pow(81, 30) - прямой ход pow(6561, 15) - прямой ход pow(43046720, 7) - прямой ход pow(1.8530202e+15, 3) - прямой ход pow(3.4336836e+30, 1) - прямой ход pow(inf, 0) - прямой ход pow(3.4336836e+30, 1) = 3.4336835956946703e+30 - обратный ход pow(1.8530202e+15, 3) = 6.362684902930465e+45 - обратный ход pow(43046720, 7) = 2.7389271546467488e+53 - обратный ход pow(6561, 15) = 1.797010106163732e+57 - обратный ход pow(81, 30) = 1.797010106163732e+57 - обратный ход pow(9, 60) = 1.797010106163732e+57 - обратный ход pow(3, 120) = 1.797010106163732e+57 - обратный ход

В целом код 2.6 ожидаемо делает тоже самое что и код 2.5 с поправкой на особенности рекурсии. Опять появились два псевдоцикла, захламление стека и есть нюансы, отличающиеся от предыдущих примеров. Теперь возведение в квадрат и if (n & 1) происходят в псевдоцикле прямого хода, а result = *tmp в псевдоцикле обратного хода и это раскидывание единой конструкции if (n & 1) result *= tmp; на два цикла лично мне ломает мозг своей нелогичностью. Точнее здесь вывод отладочной информации выглядит так, как будто он сгенерирован двумя псевдоциклами, но из-за вынесения if (n & 1) в цикл прямого хода цикл обратного хода перестаёт быть циклом и становится только похожей на цикл конструкцией специфичной именно для рекурсии. Здесь больше не получится написать полный эквивалент на основе циклов, как это сделано в коде 2.3. И это одна из причин говорить о псевдоциклах, которые внешне похожи на циклы, но внутри могут иметь логику, принципиально отличающуюся от циклов.

Ещё интересный момент - возведение в степень быстрорастущая функция поэтому логично на входе использовать float x, а на возвращаемом результате double или лучше long double, если компилятор его поддерживает. В предыдущих примерах это не вызывало никаких проблем. А в коде 2.6 float x становится накопителем результата x^{2k} и это может приводить к переполнению:

Результат для `pow_fast_rec(3, 130)` с отладочной информацией:

pow(3, 130) - прямой ход pow(9, 65) - прямой ход pow(81, 32) - ��рямой ход pow(6561, 16) - прямой ход pow(43046720, 8) - прямой ход pow(1.8530202e+15, 4) - прямой ход pow(3.4336836e+30, 2) - прямой ход pow(inf, 1) - прямой ход pow(inf, 0) - прямой ход pow(inf, 1) = inf - обратный ход pow(3.4336836e+30, 2) = inf - обратный ход pow(1.8530202e+15, 4) = inf - обратный ход pow(43046720, 8) = inf - обратный ход pow(6561, 16) = inf - обратный ход pow(81, 32) = inf - обратный ход pow(9, 65) = inf - обратный ход pow(3, 130) = inf - обратный ход

Не знаю как вам, а для меня это стало сюрпризом - мне из беглого прочтения кода 2.6 не очевидно что произойдёт именно так. Так что хотите вблизи любоваться на красивый айсберг рекурсии - будьте готовы что его подводная часть в любой момент неожиданно пробьёт борт вашего корабля.

Двигаемся дальше.
Из выводимой кодом 2.7 отладочной информации видно что итерация "pow(..., 0) - прямой ход" лишняя и её результат не используется в псевдоцикле обратного хода, а значит её можно убрать, вернув в код строку if (n == 1) return x; как это было в коде 2.2 до оптимизации. Кстати это действие отнюдь не так очевидно как может показаться на первый взгляд, потому что в оптимизированной версии используется не n - 1, a n >> 1 и в коде 2.5 условие завершения while (n != 0) не приводит к лишней итерации цикла.

Код 2.8. Уменьшаем глубину рекурсии на одну итерацию.

double pow_fast_rec_2(float x, unsigned n)
{
	if (n == 0) return 1.0; 
	if (n == 1) return x; 
	if (n & 1)
		return = x * pow_fast_rec_2(x * x, n >> 1);
	return = pow_fast_rec_2(x * x, n >> 1);
};

Теперь условием завершения прямого хода рекурсии является if (n == 1), однако просто выкинуть if (n == 0) return 1; мы не можем, потому что оно обрабатывает особый случай pow (x, 0).

Один из классических приёмов оптимизации в программировании - убрать из циклов всё лишнее. Т.е. всё что можно сделать за пределами цикла не должно оказываться внутри цикла. В этом примере конструкция if (n == 0) return 1.0 больше не является частью основного алгоритма, но при этом она попадает в псевдоцикл прямого хода рекурсии. Если бы это был обычный цикл, то вынос из него лишних действий был бы тривиален, а вот в варианте с рекурсией для этого придётся вводить вспомогательную функцию, что убивает лаконичность рекурсии и ещё больше затрудняет чтение кода.

Код 2.9. Вынос if (n == 0) return 1.0; из псевдоцикла прямого хода рекурсии.

double pow_fast_rec_lambda(float x, unsigned n)
{
	std::function<double(double, unsigned)> pow_2 = [&pow_2](double x, unsigned n)
		{
			if (n == 1) return x;
			if (n & 1)
				return x * pow_2(x * x, n >> 1);
			return pow_2(x * x, n >> 1);
		};

	if (n == 0) return 1.0;
	return pow_2(x, n);
};

Здесь введение вспомогательной функции дополнительно решает упомянутую выше проблему с float / double. Хотя её можно решить и просто использовав double x в исходной функции. В любом случае нагрузка на стек от этого увеличивается, потому что рекурсия заносит x в стек в цикле. И напомню что в варианте с циклом (код 2.5) таких проблем не возникает.

Да, в коде 2.6 - 2.9 дополнительная оптимизация по удалению одной итерации и выносу if (n == 0) выглядит надуманной "ловлей блох". Однако цель здесь не в том чтобы добиться от рекурсии максимальной производительности, а в том чтобы продемонстрировать насколько неудобно применять простые классические приёмы оптимизации программ если программа написана в формате рекурсии.

Мы ра��смотрели всего три простых примера (факториал и два варианта функции pow), а букв получилось уже много и это тоже наглядно показывает насколько применение рекурсии в программировании всё неоправданно усложняет. Но это была лёгкая разминка, а в следующей части нас ждёт встреча с настоящими айсбергами.

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