Программисты шутят, что “чтобы понять рекурсию, нужно понять рекурсию”.

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

Сегодня поговорим о том:

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

Как понять рекурсию

Чтобы понять этот прием в программировании, нужно сначала понять, что это вообще такое.

Рекурсия – это, когда функция вызывает саму себя.

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

В каких случаях функция может вызывать саму себя?

Прежде всего это делается, когда одно и то же действие нужно повторить много раз до наступления определенного условия.

Простой пример рекурсивной функции

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

Алгоритм прост – мы должны прибавлять к результату каждое следующее число. То есть, если входящий параметр 5, то функция должна отработать так: 5 + 4 + 3 + 2 +1, либо наоборот 1 + 2 + 3 + 4 + 5.

Давайте посмотрим, как такую функцию можно реализовать с помощью рекурсии.

const sum = (n) => {
  if (n === 1) {
    return 1;
  }
  return n + sum(n - 1);
}

Как видите функция принимает один параметр – n. Это число, суму чисел которого мы хотим вычислить.

Далее следует условие – это очень важная вещь. Это наш выход из функции. Если забыть про него, то функция будет работать бесконечно, стек переполнится и вы получите ошибку.

Мы начинаем с конца, каждый раз убавляя параметр в вызове функции на 1. Условие проверяет, если мы дошли до 1, то вызов рекурсивной функции заканчивается и мы возвращаем число 1 – последнее число, которое нам осталось прибавить.

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

При этом код получается коротким и лаконичным.

Таким же образом можно решить задачу по вычислению факториала числа и многие другие.

Где рекурсия нужна, а где нет

Есть задачи, которые можно решить только с помощью рекурсии, однако их не так много.

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

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

Почему рекурсия – это не всегда хорошо?

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

Такую же ошибку вы получите, если забудете написать условие выхода из функции или напишите его некорректно.

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

Проектирование рекурсивной функции

Если вы решаете написать рекурсивную функцию для решения той или иной задачи, то:

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

Исходя из всего вышенаписанного можно сделать следующие выводы:

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

Надеюсь этот пост был вам полезен. Удачи с рекурсией.