0Pricing
Coding Interview Prep · Урок

Структура рекурсии: базовый случай, доверие, построение

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

«Структура рекурсии: базовый случай, доверие, построение» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Почему рекурсия кажется сложной

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

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

Шаг 1: Определите базовый случай

Базовый случай — это простейшие входные данные, для которых ответ известен без дальнейшей рекурсии. Каждая рекурсивная функция должна иметь хотя бы один базовый случай; без него функция будет вызывать себя бесконечно (переполнение стека). Хорошие базовые случаи: пустой список, один элемент, n == 0, n == 1 или задача сводится к тривиальному тождеству.

Сначала запишите базовый случай, а уже затем любую рекурсивную логику. Определите его, спросив себя: «Какую самую маленькую версию этой задачи я могу решить сразу?»

# Base cases for common problems
def factorial(n):
    if n == 0:          # base case: 0! = 1
        return 1
    # ... recursive step below

def sum_list(lst):
    if not lst:         # base case: sum of empty list is 0
        return 0
    # ...

def height(node):
    if node is None:    # base case: height of null node is 0
        return 0
    # ...

print('Base cases identified')

Шаг 2: Доверьтесь рекурсивному вызову

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

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

# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11  (we TRUST this, don't trace it)
# Build: 3 + 11 = 14

# So:
def sum_list(lst):
    if not lst:
        return 0
    # Trust that sum_list(lst[1:]) returns sum of the rest
    return lst[0] + sum_list(lst[1:])

print(sum_list([3, 1, 4, 1, 5]))  # 14

Шаг 3: Постройте решение

Шаг построения объединяет доверенный результат подзадачи с вкладом текущего элемента, чтобы получить ответ для всех входных данных. Обычно это одна строка: применить операцию к текущему элементу и результату рекурсивного вызова. Распространённые варианты построения: добавить к сумме, добавить в начало списка, увеличить счётчик, объединить два промежуточных результата.

def factorial(n):
    if n == 0:
        return 1
    # Trust: factorial(n-1) gives (n-1)!
    # Build: n * (n-1)! = n!
    return n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    # Trust: power(base, exp-1) gives base^(exp-1)
    # Build: base * base^(exp-1) = base^exp
    return base * power(base, exp - 1)

print(factorial(6))    # 720
print(power(2, 10))    # 1024

Применение схемы к сумме цифр

Задача: вычислить сумму цифр неотрицательного целого числа. Базовый случай: n == 0 → сумма равна 0 (или n < 10 → само число). Доверие: sumDigits(n // 10) возвращает сумму всех цифр, кроме последней. Построение: прибавить последнюю цифру n % 10 к доверенному результату. Схема даёт решение в три декларативных шага.

def sumDigits(n):
    if n < 10:
        return n            # base case: single digit
    # Trust: sumDigits(n // 10) gives sum of all digits except last
    # Build: add the last digit
    return n % 10 + sumDigits(n // 10)

print(sumDigits(0))      # 0
print(sumDigits(7))      # 7
print(sumDigits(123))    # 6
print(sumDigits(9999))   # 36

Фибоначчи: две подзадачи

Для вычисления чисел Фибоначчи нужны два рекурсивных вызова: fib(n-1) и fib(n-2). Применим схему: базовые случаи — fib(0) = 0 и fib(1) = 1. Доверие: оба меньших вызова возвращают правильные числа Фибоначчи. Построение: вернуть их сумму. Эта наивная реализация имеет временную сложность O(2^n) — мы исправим это на уроке о мемоизации.

def fib(n):
    if n <= 1:
        return n      # base cases: fib(0)=0, fib(1)=1
    # Trust both smaller sub-problems
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f'fib({i}) = {fib(i)}')  # 0,1,1,2,3,5,8,13

Рекурсивный разворот строки

Задача: рекурсивно развернуть строку. Базовый случай: пустая строка или один символ — они уже развернуты. Доверие: reverse(s[1:]) возвращает разворот всей строки после первого символа. Построение: выполнить append, чтобы добавить первый символ в конец развернутого суффикса. Схема даёт решение из трёх строк.

def reverse_str(s):
    if len(s) <= 1:
        return s            # base case
    # Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
    # Build: append first character at end
    return reverse_str(s[1:]) + s[0]

print(reverse_str(''))        # ''
print(reverse_str('a'))       # 'a'
print(reverse_str('hello'))   # 'olleh'
print(reverse_str('racecar')) # 'racecar'

Рекурсивный подсчёт вхождений

Задача: рекурсивно подсчитать количество вхождений целевого значения в списке. Базовый случай: пустой список — количество равно 0. Доверие: count(lst[1:], target) возвращает количество в хвосте списка. Построение: добавить 1, если первый элемент совпадает с целевым значением, иначе добавить 0. Каждый рекурсивный шаг приближает нас к базовому случаю, уменьшая размер списка на 1.

def count_occurrences(lst, target):
    if not lst:
        return 0
    # Trust: count in rest of list is handled recursively
    # Build: add 1 if first element matches, else 0
    return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)

print(count_occurrences([1, 2, 3, 2, 4, 2], 2))  # 3
print(count_occurrences([], 5))                    # 0
print(count_occurrences([7, 7, 7], 7))             # 3

Проверка сортировки списка

Задача: рекурсивно проверить, отсортирован ли список по возрастанию. Базовый случай: список из 0 или 1 элемента всегда отсортирован. Доверие: is_sorted(lst[1:]) сообщает, отсортирован ли хвост списка. Построение: список отсортирован, если первый элемент <= второго AND хвост отсортирован. Это наглядный пример, где на шаге построения используется логическое AND двух условий.

def is_sorted(lst):
    if len(lst) <= 1:
        return True
    # Trust: is_sorted(lst[1:]) tells us if tail is sorted
    # Build: head <= second element AND tail is sorted
    return lst[0] <= lst[1] and is_sorted(lst[1:])

print(is_sorted([]))           # True
print(is_sorted([1]))          # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False

Рекурсивный двоичный поиск (повторение)

Двоичный поиск, выраженный рекурсивно с помощью этой схемы: базовый случай: lo > hi → элемент не найден (вернуть -1). Доверие: рекурсивный вызов для правильной половины находит целевой элемент или возвращает -1. Построение: вычислить середину, сравнить значения и вызвать функцию для соответствующей половины. Рекурсивная форма наглядно показывает структуру «разделяй и властвуй», хотя в рабочем коде предпочтительна итеративная форма с памятью O(1).

def binary_search(arr, target, lo, hi):
    if lo > hi:          # base case: search space exhausted
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    # Trust both halves return correct results
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))   # 3
print(binary_search(arr, 4, 0, len(arr) - 1))   # -1

Когда использовать рекурсию, а когда итерацию

Рекурсия особенно эффективна, когда задача естественным образом разбивается на меньшие подзадачи того же типа (деревья, стратегия «разделяй и властвуй», поиск с возвратом). Итерация предпочтительна, когда: глубина рекурсии велика (в Python есть риск переполнения стека, поскольку по умолчанию допускается около 1000 уровней), рекурсивная и итеративная версии одинаково понятны или задача представляет собой простой цикл (factorial, Фибоначчи без мемоизации).

Полезное практическое правило: если дерево рекурсии естественно рисуется, используйте рекурсию. Если дерево представляет собой прямую линию (хвостовая рекурсия), преобразуйте её в итерацию.

import sys

# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit())  # 1000

# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
    total = 0
    for x in lst:
        total += x
    return total

big = list(range(2000))
print(sum_list_iter(big))  # 1999000 — no stack overflow

Быстрая проверка

Проверьте, насколько вы поняли концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию», изложенные в этом уроке.

Итоги урока

В этом уроке вы узнали: схема из трёх шагов — это базовый случай (простейший известный ответ), доверие (предполагаем, что подзадача решена) и построение (объединяем текущий элемент с доверенным результатом), сначала записывайте базовые случаи и не пытайтесь мысленно прослеживать всё дерево вызовов, а также используйте итерацию, когда глубина рекурсии грозит переполнением стека или рекурсивная и итеративная формы одинаково понятны. Далее мы подробно рассмотрим стек вызовов.

Часто задаваемые вопросы

Урок «Структура рекурсии: базовый случай, доверие, построение» бесплатный?

Да — полный текст урока «Структура рекурсии: базовый случай, доверие, построение» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 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 — локальная установка не требуется.

Все уроки этого курса

  1. Структура рекурсии: базовый случай, доверие, построение
  2. Визуализация стека вызовов
  3. Компромиссы рекурсивного и итеративного подходов
  4. Мемоизация: кэширование результатов рекурсии
← Назад к Coding Interview Prep