Рекурсивное мышление: база и рекурсия
Разбивайте задачу на меньшие копии
«Рекурсивное мышление: база и рекурсия» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое рекурсия
Рекурсия — это функция, которая решает задачу, вызывая себя для меньшей части, пока эта часть не станет достаточно маленькой для прямого ответа. 🌀
Доверьтесь меньшей копии
Ключевой приём — довериться рекурсивному вызову: предположить, что он уже работает для меньших входных данных, а затем построить на его результате свой ответ.
В рекурсии всегда нужен базовый случай
Базовый случай — это наименьшие входные данные, для которых Вы отвечаете без рекурсивного вызова. Без него функция вызывает себя бесконечно и завершается с ошибкой.
Рекурсивный случай
Рекурсивный случай уменьшает задачу и вызывает функцию для меньшей версии. Каждый вызов должен приближать Вас к базовому случаю.
Факториал как первый пример
Здесь факториал демонстрирует обе части: базовый случай для нуля и рекурсивный вызов для n минус один.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Как работает стек вызовов
Каждый вызов ждёт в стеке вызовов, пока не завершится его внутренний вызов. Самый глубокий вызов завершается первым, после чего результаты возвращаются вверх по стеку.
Следите за глубиной рекурсии
По умолчанию Python ограничивает глубину рекурсии примерно 1000 вызовами. Для глубокой рекурсии в соревнованиях нужен sys.setrecursionlimit, чтобы избежать ошибки времени выполнения.
import sys
sys.setrecursionlimit(300000)Делайте шаг вперёд при каждом вызове
В корректной рекурсии входные данные всегда уменьшаются и приближаются к базовому случаю. Если размер снова становится тем же, функция зацикливается навсегда. ⚠️
Рекурсивно суммируйте список
Эта рекурсивная сумма отделяет первый элемент, а затем поручает вызову сложить оставшуюся часть списка.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Деревья рекурсии показывают ветвление
Когда функция выполняет более одного вызова, работа образует дерево рекурсии. Его размер показывает общую стоимость вычислений.
Повторяющаяся работа может замедлить программу
Наивный алгоритм вычисления чисел Фибоначчи снова и снова пересчитывает одни и те же значения, что приводит к экспоненциальному времени работы. Мемоизация этих результатов мгновенно решает проблему.
Быстрая проверка
Что произойдёт, если у рекурсивной функции нет базового случая?
Повторение: две части, одна идея
Вы узнали, что рекурсии нужен базовый случай для остановки и рекурсивный случай, который уменьшает входные данные. Доверьтесь меньшему вызову — и остальное последует само. 🎯
Часто задаваемые вопросы
Урок «Рекурсивное мышление: база и рекурсия» бесплатный?
Да — полный текст урока «Рекурсивное мышление: база и рекурсия» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Рекурсивное мышление: база и рекурсия»?
Разбивайте задачу на меньшие копии Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Рекурсивное мышление: база и рекурсия»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рекурсивное мышление: база и рекурсия
- Генерация всех подмножеств
- Перестановки и идея задачи о N ферзях
- Сокращение поиска ради соблюдения лимита времени