Где применяется
1. Задача
В прошлой группе уроков ты строил стек сам: стопку, на которую кладёшь работу и с которой её снимаешь. Рекурсия (вызов функцией самой себя) даёт такой же стек, только его ведёт язык. Каждый раз, когда функция вызывает саму себя, среда исполнения кладёт незаконченную работу на стек. Каждый раз, когда функция возвращает результат, среда снимает её со стека. Ты пользуешься стеком, не управляя им вручную, и в этой задаче это очень удобно.
Тебе нужен общий размер папки. Если в ней 4 файла, всё просто: прочитай размер каждого и сложи. Но в папке лежат папки, в них ещё папки, и насколько глубоко это идёт, ты не знаешь, пока не заглянешь.
Обычные циклы тут не справляются. Чтобы написать вложенные циклы, нужно заранее знать форму данных. А здесь форма такая: глубина неизвестна, и на каждом уровне может быть сколько угодно веток. Нельзя вложить for в for пять раз и надеяться, что пяти уровней хватит.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитrecurse(4)recurse(n) складывает n + (n - 1) + ... + 0. Каждый вызов делает один шаг и передаёт n поменьше следующему вызову. Начинаем с recurse(4).
Как узнать
Эти слова в условии значат этот паттерн
- задача определена через меньшую версию самой себя
- вложенная/древовидная структура для обхода (папки, выражение, связный список)
- нужно посчитать сумму/количество/глубину по всем подэлементам
- естественное деление на базовый случай и рекурсивный (факториал, Фибоначчи, глубина дерева)
Похоже, но не то
- Рекурсия с мемоизацией (Recursion with memoization)
Мемоизация это то же самое плюс кеш прошлых ответов. Она нужна, когда аргумент повторяется.
- Бэктрекинг (Backtracking)
Бэктрекинг отменяет выбор после того, как его исследовал. Обычная рекурсия ничего не отменяет.
- Стек (LIFO) (Stack (LIFO))
Стек вызовов это стек, который вы не писали. Свой стек снимает ограничение по глубине.
- Обход дерева (Tree traversal)
На деревьях рекурсия дешевле и понятнее всего. Та страница про три порядка посещения.
Глубина примерно до 10000 в браузере безопасна. Глубже стоит переписать рекурсию циклом.
На LeetCode
Задачи, где ответ для целого складывается из ответов для меньших частей той же формы, например вложенных списков или цепочек подчинения. Напиши базовый случай, вызови функцию на каждой части и сложи результаты.
Учебная рекурсия с двумя базовыми случаями, и n не больше 30, так что простая версия проходит.
Пример с руководителем из урока, где итог сотрудника равен его собственной важности плюс итоги прямых подчинённых.
На каждом вызове дели степень пополам и возводи результат в квадрат, тогда глубина будет log n, а не n.
Разверни вложенный список рекурсией в конструкторе, это тот же обход, что перечисление файлов в папках.