Рекурсия со строками и списками
Список — это первый элемент и хвост a[1:], а хвост — тоже список, только короче. Сумма списка — первый элемент плюс сумма хвоста, а у пустого списка сумма 0.
Пустой список в if — ложь, поэтому базовый случай пишут if not a:. Со строками так же: s[0] — первый символ, s[1:] — остальные.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])
print(total([3, 1, 4]))
print(total([]))
Рекурсия удобна, когда число разбирают по частям: двоичная запись n — это двоичная запись n // 2 и в конце цифра n % 2.
Так же рекурсия обходит вложенные списки: элемент-список функция разбирает тем же способом, что и весь список. Проверка type(x) == list отличает список от числа.
def binary(n):
if n < 2:
return str(n)
return binary(n // 2) + str(n % 2)
def deep_sum(a):
total = 0
for x in a:
if type(x) == list:
total += deep_sum(x)
else:
total += x
return total
print(binary(13))
print(deep_sum([1, [2, 3], [[4], 5]]))
Итог урока. Строку и список рекурсия разбирает на первый элемент и хвост a[1:] или на края и середину s[1:-1]. Базовый случай — пустой или очень короткий список.
Число разбирают на n // 2 и n % 2 или на n // 10 и n % 10, вложенный список — тем же способом, что и весь.
В следующем уроке — перебор вариантов: рекурсия перечислит все строки, наборы и перестановки.
Урок пройден
Рекурсия со строками и списками
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Рекурсия со строками и списками
Рекурсия со строками и списками в Python: первый элемент и хвост a[1:], края и середина s[1:-1], двоичная запись числа, вложенные списки. В 6 заданиях вы найдете наибольшее число, проверите палиндром, переведете число в двоичную запись, посчитаете буквы, перевернете список и прочитаете программу: что она выведет?