Рекурсия в Python
В программировании есть такое понятие, как рекурсия - когда функция вызывает сама себя.
Пример . Простая рекурсия со счетчиком
Давайте выведем с помощью рекурсии числа от 1
до 10:
i = 1
def func():
global i
print(i)
i++
if i <= 10:
func() # здесь функция вызывает сама себя
func()
Давайте обсудим, как работает этот код.
У нас есть глобальная переменная i
и функция func, внутри которой в консоль
выводится содержимое переменной i,
а затем к ней прибавляется единица.
Если наша переменная i меньше или
равна 10, то функция вызывается повторно.
Так как переменная i - глобальная,
то при каждом новом вызове функции в ней
будет заданное при предыдущем вызове значение
переменной i.
Получится, что функция будет вызывать сама
себя до тех пор, пока i не станет
больше 10.
Учтите, что в нашем случае нельзя функцию
запустить без if - если это сделать,
то получится бесконечный вызов функций.
Пример . Рекурсия для вывода элементов вложенных списков
Наиболее часто рекурсии применяются для перебора списков разной степени вложенности. Пусть у нас есть следующий список:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Давайте создадим функция, которая переберет его.
В ней сначала нужно задать условие, чтобы
элемент, который является примитивом, т.е. просто извлеченным
из списка числом, выводился в консоль.
А если элемент является объектом, например,
вложенным списком, то пусть в этом случае
функция вызовет сама себя, т.е. произойдет
рекурсия. Для проверки типа элемента
применим функцию isinstance.
Только для нашего примера в первый параметр
isinstance пропишем el, а
вторым - тип list:
def func(lst):
for el in lst:
if isinstance(el, list):
func(el)
else:
print(el)
При вызове функции выведется ряд всех чисел из вложенного списка:
func(lst) # выведет 1, 2, ... 8, 9
Пример . Рекурсия для операций с элементами вложенных списков
Рекурсии можно применять и для различных операций с элементами вложенных списков. Пусть у нас есть следующий список:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Давайте получим сумму всех его элементов.
Для этого в функции объявим переменную
res, в которую будет накапливаться сумма
чисел. В условии пропишем, что если
элемент является сложным объектом,
то он попадает в параметре функции
func и прибавляется к сумме.
Это значит, что элемент будет находиться
в рекурсии пока не станет примитивом.
И в этом случае он просто прибавится к
сумме, записанной в res:
def func(lst):
res = 0
for el in lst:
if isinstance(el, list):
res += func(el)
else:
res += el
return res
Давайте вызовем функцию и выведем ее результат в консоль:
print(func(lst)) # выведет 45
Пример . Рекурсия для накопления в список
С помощью рекурсии можно разложить вложенные списки в один одномерный список. Пусть у нас есть следующий список:
lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]
Давайте пропишем в функции
пустой список res, в который будут накапливаться
элементы исходного списка. Далее
запустим цикл и зададим условие -
если элемент является списком,
то он попадет в метод extend.
Этот метод присоединяет элементы одного списка
в конец второго списка, т.е.
элементы вложенного списка попадут
в конец списка res:
def func(lst):
res = []
for el in lst:
if isinstance(el, list):
res.extend(func(el))
else:
res.append(el)
return res
print(func(lst))
Результат выполненного кода:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Практические задачи
Выведите все числовые элементы словаря произвольного уровня вложенности:
{
'a': {
'b': 1,
'c': 2,
'd': {
'e': 3,
'f': 4
}
},
'j': {
'h': 5,
'k': 6,
},
'l': 7
}
Найдите сумму элементов словаря из предыдущей задачи.
Получите список примитивных элементов словаря из предыдущей задачи.