Что такое рекурсия
easy

Что такое рекурсия

Это дом, который построил Джек.

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

Дом, который построил Джек

Чтобы было понятнее, что такое рекурсия, возьмём стихотворение Самуила Маршака «Дом, который построил Джек»:

Вот дом,
Который построил Джек.

А это пшеница,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

А это весёлая птица-синица,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

Вот кот,
Который пугает и ловит синицу,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

Вот пёс без хвоста,
Который за шиворот треплет кота,
Который пугает и ловит синицу,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек. …

Смотрите, что в нём интересного: каждая часть стихотворения состоит из нового начала и точного повторения того, что уже было до этого. Сначала у нас был только дом, который построил Джек — это нулевой уровень рекурсии, или вложенности.

Нулевой уровень:

Вот дом,
Который построил Джек.

Обозначим его за [0] и дальше будем увеличивать это число для каждого уровня. Следите за уровнями.

Первый уровень:

А это пшеница,
Которая в тёмном чулане хранится [0]

Чтобы получить полноценное продолжение, нам нужно взять предыдущий уровень и подставить его сюда:

А это пшеница,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

Второй уровень:

А это весёлая птица-синица,
Которая часто ворует пшеницу,
[1]

Если мы будем разворачивать стих, то на первом проходе получим такое:

А это весёлая птица-синица,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
[0]

А на втором у нас уже появится полноценный стих:

А это весёлая птица-синица,
Которая часто ворует пшеницу,
Которая в тёмном чулане хранится
В доме,
Который построил Джек.

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

Рекурсия в программировании

Допустим, нам нужно посчитать сумму всех чисел от 1 до какого-то числа. Можно это сделать в цикле, а можно сделать универсальную функцию с рекурсией. Ей будет достаточно указать на входе число, до которого нужно всё посчитать, а она сама сделает всё остальное.

Сначала запишем это на JavaScript, а потом разберёмся с тем, как работает эта магия:

function rec(x) {
  if (x == 1) { return (1) }
  else {
    return x + rec(x - 1);
  }
}
rec(10);

Первая строчка — объявление функции function rec(x). Здесь всё как обычно — указываем название и говорим, что на вход будет поступать какая-то переменная, с которой можно работать.

Затем мы организуем нулевой уровень — тот, где рекурсия начинается: if (x == 1) {return(1)}. Он говорит нам: если на вход поступит единица, то возвращаем единицу. Это логично — сумма всех чисел от 1 до 1 равна единице. Это как дом, который построил Джек — всё в итоге сведётся к этому.

А дальше идёт самое интересное — если мы не дошли до единицы, то мы берём значение x и складываем его с результатом этой же функции, но от предыдущего значения. Если мы, например, считаем rec(10), то эта команда сделает так:

  1. Проверит, дошли ли до единицы.
  2. Если не дошли — сложит 10 и значение rec(9).
  3. Для этого она проверит, дошли ли до единицы.
  4. Если не дошли — сложит 9 и значение rec(8).
  5. Для этого она проверит…
  6. Ура, мы дошли до единицы и возвращаем единицу обратно.
  7. К этому моменту рекурсия уже дошла до команды 2 + rec(1). Она получает в ответ единицу, складывает 2 и 1 и возвращает результат на уровень выше.
  8. На уровне выше была команда 3 + rec(2). Она получает в ответ 3, складывает 3 и 3 и возвращает результат на уровень выше.
  9. На последнем уровне была команда 10 + rec(9). Она получает от предыдущего уровня результат 45, складывает 10 и 45 и получает результат 55.
  10. Ура, рекурсия закончилась.

Попробуйте сами вставить код в консоль и посмотрите на результат.

Особенности рекурсии

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

Иногда программист увлекается рекурсией и забывает прописать выход из неё. В результате рекурсия бесконечно углубляется саму в себя, забирает в себя все ресурсы и программа падает. Говорят, что так образуются чёрные дыры, в которых всё исчезает.

Бывают моменты, когда рекурсия — это единственный способ выполнить нужную задачу. Например, при парсинге HTML-кода или для построения дерева зависимостей.

Что дальше

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

Текст

Михаил Полянин

Редактор

Михаил Полянин

Корректор

Ирина Михеева

Иллюстрация

Даня Берковский

Вёрстка

Мария Дронова

Сделать так, чтобы все узнали об этой статье

Виталий Вебер

Джек, который построил дом

Павел Федоров

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
easy