Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
А это подборки моих материалов на канале
Рекурсия и простейшие примеры на Python
С рекурсией на моём канале мы уже встречались. См. например
Но я наметил целую серию статей об рекурсии на Python. А сегодня просто знакомство с рекурсивными алгоритмами. Простые программы.
Рекурсивный алгоритм предполагает вызов функции из самой себя или через другую функцию.
Рекурсия предполагает соблюдение некоторых условий:
- Количество вызовов функции должно быть конечным. В противном случае будет исчерпан стек. Python по-умолчанию ограничивает количество рекурсивных вызовов. К это проблеме мы вернёмся в одной из следующих статей.
- Рекурсия в общем случае предполагает, что вызов функции должен отличаться от предыдущего. Это достигается использованием глобальных переменных либо изменением параметров вызова. Ниже мы продемонстрируем данное положение.
Рассмотрим несколько примеров с рекурсией. В данных случаях рекурсия абсолютно излишня и служит только в качестве демонстрации.
Программа выводит все элементы списка в столбик.
По сути мы получили рекурсивную замену обычного цикла.
На чтобы хотелось обратить внимание. Вот
if k == l:
Эта строка обеспечивает конечное количество рекурсивных вызовов. Лишний раз отметим, что длина списка может быть очень большой и стека, который выделяется интерпретатором Python, может не хватить. В данном случае естественно использовать просто цикл.
Следующий пример вычисления суммы элементов списка
Тут важно отметить, что сумма сохраняется в глобальной переменной. Хочется отметить, что использование глобальных переменных часто позволяет упростить текст рекурсивной функции.
Следующий пример очень интересен. Прежде всего тем, что вычисляя длину списка, мы не используем глобальную переменную. Это несколько усложняет рекурсивный алгоритм. Точнее, его восриятие.
Строка
return 1 + lnn(ls[1:])
Данная строка интересна двумя моментами.
1. Очередной вызов lnn(ls[1:]) уменьшает размер списка. На очередном шаге он просто становится пустым. Строка
if not ls:
и определяет, что список стал пустым и заканчивает рекурсию.
2. Возврат из рекурсии происходит пошагово. И на каждом шаге в операторе return добавляется ещё одна единица плюсом. В результате при полном возврате из рекурсии возвращается длина списка.
А этот пример демонстрирует предыдущий подход, но уже для вычисления суммы элементов списка.
Надеюсь представленные примеры заинтересуют вас в использовании рекурсивных алгоритмов. Тем более, что иногда без них весьма трудно обойтись.
Хорошего программирования. Оставляйте свои комментарии, не забывайте про лайки и подписывайтесь на мой канал programmer's notes.