Что работает быстрее: цикл или рекурсия? Измеряем производительность

Возьмем какую-нибудь несложную задачку, которую можно реализовать двумя способами: с помощью цикла и с помощью рекурсии.

Тривиальная задача сравнения метода вычисления факториал с помощью цикла и метода вычисления факториала с помощью рекурсии. Берется некоторое число n, для которого вычисляем факториал разными способами.

Вычисления засовываем в цикл с 1000 итераций, чтобы снизить погрешность.

Засекаем время с помощью метода Milliseconds() (библиотека Utils). Выводим результаты. В большинстве случаев рекурсия выполняется быстрее.

[ Язык реализации: Pascal ]

Полный код

Предлагаю обсудить в комментариях, почему так происходит?

Код можно также переписать на C/C++. Об этом я уже писал в одной из первых статей:
Время работы алгоритма простого поиска элемента в массиве. Время работы кода на C++

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

Рекурсия

Рекурсией в программировании называется метод, вызывающий сам себя. Несмотря на простоту определения, этот подход достаточно сложен для понимания, поскольку человеку не свойственен подобный стиль мышления. Более того, существуют рекурсии разных типов, что вносит еще большую путаницу. Чаще всего применяются рекурсии следующих двух типов:

• Головная рекурсия— рекурсивный вызов выполняется ближе к началу метода и является одним из первых обрабатываемых объектов. Поскольку он вызывает сам себя, ему приходится полагаться на результаты предыдущей операции, помещенной в стек вызовов. Из-за использования стека вызовов существует вероятность переполнения стека, если стек вызовов недостаточно велик.
• Концевая рекурсия— рекурсивный вызов выполняется в конце и является последней строкой обрабатываемого кода. Этот метод не использует стек вызовов независимо от глубины рекурсии.

В математике рекурсия распространена достаточно широко, поэтому проще будет объяснить ее на примере рекурсивного вызова. Выражение 5! (факториал числа 5) можно записать следующим способом:

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

Приведен пример вычисления 5! с помощью головной рекурсии. Пример на Java

Каждый рекурсивный вызов должен быть завершен и помещен в стек вызовов до расчета факториала. Например, Java будет интерпретировать каждый вызов метода getFactorial следующим образом (каждая строка представляет объект, находящийся в стеке вызовов):

Как этот алгоритм головной рекурсии интерпретирует компилятор

Теперь приведем код для реализации концевой рекурсии

Пример вычисления 5! с помощью концевой рекурсии

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

Как этот алгоритм концевой рекурсии интерпретирует компилятор

Цикл

Языки программирования предоставляют циклы нескольких разных типов, очень хорошо знакомых большинству программистов. В языке Pascal существуют for, while и repeat циклы. В языке программирования Java и других С-подобных ЯП имеются циклы for, do и while.

Цикл — это многократное исполнение нескольких операторов. Циклы не заносят данные в стек вызовов независимо от числа исполнений цикла. Важным отличием циклов от рекурсивных функций является тот факт, что циклы используют для подсчета числа исполнений итератор, а рекурсивные функции для определения момента выхода должны выполнять сравнение результатов. Другим важным отличием является возможность применения в циклах фильтров и прочих селекторов. Примером такой ситуации может служить цикл foreach.

Что лучше?

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

Области применения рекурсии

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

Заключение

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

Спасибо, что дочитали до конца :) Если вам нравятся такие разборы, и вы хотите видеть их чаще, то оставьте обратную связь (лайки, комментарии, ваши мысли).

Еще много полезного и интересного вы сможете найти на ресурсах:

Репетитор IT mentor в VK

Репетитор IT mentor в Instagram

Physics.Math.Code (Дзен)

Physics.Math.Code в контакте (VK)

Physics.Math.Code в telegram

Physics.Math.Code в YouTube