РусҚаз

Рекурсия

Информатика · 9 класс · Алгоритмы обработки · Урок 4 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

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

Маленький ребёнок на ковре раскрывает деревянную матрёшку, вокруг выстроены в ряд всё меньшие и меньшие фигурки.

Зачем это нужно

Рекурсия прячется во множестве технологий: так обходят папки на диске, разбирают веб-страницы и программный код, строят деревья решений в играх и рисуют фракталы в компьютерной графике. Многие быстрые алгоритмы сортировки и поиска устроены по принципу «раздели задачу пополам и реши каждую половину тем же способом». ИИ легко напишет рекурсивную функцию, но заметить, что у неё нет базового случая и она уйдёт в бесконечность, или что она переполнит память, сможет только тот, кто понимает механизм. Умение разбивать большую задачу на такие же маленькие — ключевой навык инженера и исследователя.

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

Как это работает

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

Повар в кафе снимает тарелки с высокой стопки по одной, начиная с самой верхней, на кухне шумно и светло.

Немного истории

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

Математик девятнадцатого века в сюртуке сидит у окна в парижской комнате и задумчиво перекладывает деревянные диски на трёх колышках.

Формула: факториал

Факториал эн — это произведение всех чисел от одного до эн. Заметь: если ты уже знаешь факториал эн минус один, достаточно умножить его на эн, — вот и рекурсия: эн факториал равно эн умножить на эн минус один факториал. Чтобы вызовы не шли бесконечно, нужен базовый случай: ноль факториал равен единице, его компьютер знает сразу. Буква эн — целое неотрицательное число, единиц у него нет. Если увеличить эн на один, ответ вырастет в эн плюс один раз, поэтому факториал растёт невероятно быстро.

  • n! = n · (n − 1)!n — целое неотрицательное число, —
    n! — факториал: произведение чисел от 1 до n, —
  • 0! = 10! — базовый случай рекурсии, —

Формула: число ходов

Сколько ходов нужно, чтобы перенести башню из эн дисков? Смотри на рецепт: дважды переносим башню из эн минус одного диска и делаем один ход самым большим диском. Значит, каждый новый диск удваивает работу и добавляет ещё один ход, и в итоге получается два в степени эн минус один. Буква эн — число дисков, ответ — минимальное число ходов. Один диск — один ход, два диска — три хода, три — семь, а четыре диска — пятнадцать; добавишь ещё один диск — ходов станет больше чем вдвое.

  • ходов = 2ⁿ − 1n — число дисков, —
    2ⁿ − 1 — минимальное число ходов, —

Что будем делать на практике

А теперь давай попробуем выполнить практическое задание. Перед тобой три стержня: А — откуда переносим, Б — запасной, В — куда переносим, а на стержне А стоит башня из четырёх дисков, самый большой внизу. Нужно перенести всю башню на стержень В ровно за пятнадцать ходов, перекладывая по одному диску и никогда не кладя больший диск на меньший. Подумай рекурсивно: чтобы освободить самый большой диск, куда сначала нужно убрать три верхних? А чтобы убрать три, что делать с двумя верхними? Следи за счётчиком ходов — если уложишься в пятнадцать, значит, ты повторил формулу два в степени четыре минус один. Если что-то осталось непонятным — ничего страшного, спроси меня о чём угодно, я отвечу. Не переживай.

Задание в опыте

Перенесите башню из 4 дисков со стержня A на стержень C ровно за 15 ходов. Больший диск нельзя класть на меньший.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Алгоритмы обработки

  1. Поиск: линейный и бинарный
  2. Сортировки
  3. Сложность алгоритма
  4. Рекурсия