За три секунды до баннера идёт отсчёт. Вместо цикла запусти вот это:
def countdown(n):
if n == 0:
print("Молитва открыта!")
return
print(n)
countdown(n - 1)
countdown(3)
3
2
1
Молитва открыта!
Функция countdown внутри себя вызывает countdown, только с числом поменьше. Так продолжается, пока число не дойдёт до нуля и функция не остановится. Такой приём называется рекурсией.
У любой правильной рекурсивной функции две части:
n == 0 в примере);n - 1).Без базового случая функция вызывала бы себя бесконечно, и Python остановил бы её сам:
def forever(n):
return forever(n + 1)
forever(0)
RecursionError: maximum recursion depth exceeded
Python разрешает по умолчанию примерно тысячу вложенных вызовов: у каждого вызова своё место в памяти, и безграничной «лесенки» не бывает.
def fact(n):
if n <= 1:
return 1
return n * fact(n - 1)
print(fact(5)) # → 120 5 · 4 · 3 · 2 · 1
Как это читать: «факториал n — это n, умноженное на факториал n - 1, а факториал единицы равен единице». Каждый вызов ждёт ответа следующего и потом умножает. Попробуй мысленно разложить fact(3): 3 * fact(2) → 3 * (2 * fact(1)) → 3 * (2 * 1) → 6.
def to_binary(n):
if n < 2:
return str(n)
return to_binary(n // 2) + str(n % 2)
print(to_binary(10)) # → 1010
Идея та же: запись числа — это запись его половины плюс последняя цифра. Здесь порядок важен: цифра дописывается справа после возврата из рекурсии.
def total(items):
result = 0
for item in items:
if isinstance(item, list): # вложенный список — сумма его самого
result += total(item)
else:
result += item
return result
print(total([1, [2, 3], [4, [5]]])) # → 15
Когда глубина вложенности заранее не известна (списки в списках, папки в папках, деревья), рекурсия самая естественная: «обработай то, что видишь, а вложенное отдай той же функции». С такими данными мы встретимся в разделе про файлы и в алгоритмах. Заметь, что isinstance(item, list) проверяет, является ли значение списком.
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
Числа Фибоначчи, записанные так, красивы, но на fib(35) программа заметно задумается: одни и те же значения считаются снова и снова. Правило: если задачу так же легко решить циклом и вложенность не растёт — выбирай цикл, он быстрее и не упирается в предел глубины. Рекурсия нужна там, где данные сами устроены как «матрёшка».
count_down_up(n), которая печатает числа от n до 1, а потом обратно от 1 до n. Подумай, куда поставить print относительно вызова.power(a, n) — возведение в степень через умножение и рекурсию (без **).n fact(n) перестаёт работать из-за предела рекурсии? Подсказка: он около тысячи.За n секунд до начала баннера идёт отсчёт: выводятся числа от n до 1 по одному в строке, а после них — Молитва открыта!. Если n равно 0, выводится только последняя фраза.
Напиши рекурсивную функцию countdown(n) (без циклов) и вызови её для числа, прочитанного из ввода.
Пример. Ввод 3, вывод:
3
2
1
Молитва открыта!Заготовка (кнопка у блока отправит её в песочницу):
# 1. Функция countdown(n): базовый случай — когда считать нечего; иначе выведи число и вызови себя с n - 1
# 2. Прочитай n и вызови функцию
Хиличурлы передают числа двоичным кодом: нули и единицы. Напиши рекурсивную функцию to_binary(n), которая возвращает двоичную запись неотрицательного числа в виде строки (для 0 — 0, для 5 — 101). Идея: двоичная запись числа — это запись числа n // 2, к которой справа дописана цифра n % 2.
Программа читает число n (от 0 до 255) и выводит две строки: код и количество единиц в нём.
Пример. Ввод 10, вывод:
Двоичный код: 1010
Единиц: 2Заготовка (кнопка у блока отправит её в песочницу):
# 1. Функция to_binary(n): базовый случай — маленькое число записывается само; иначе склей запись половины и последнюю цифру
# 2. Прочитай число, получи код и посчитай единицы
Рекурсия — функция, вызывающая себя. Ей нужны базовый случай (когда пора остановиться) и шаг, приближающий к нему; без базового случая получим RecursionError. Рекурсивные функции могут и печатать, и возвращать значения; порядок «действие до вызова» и «после вызова» меняет результат. Для вложенных данных рекурсия естественна, для простых повторов лучше цикл.
С функциями разобрались. Дальше — как программа справляется с ошибками и работает с файлами.