Что бы понять что такое рекурсия надо понять что такое рекурсия.
Рекурсия — процесс повторения элементов самими элементами. В реальном мире подобное можно наблюдать если зайти в зеркальный лабиринт где есть зеркало №1 которое отражает зеркало №2 в котором отражено зеркало №1 которое… и т.д. Или если вэб-камеру направить на монитор, на который выводится изображение с неё.
В программировании Рекурсия – это вызов функции из неё же самой (из тела этой функции).
Рекурсию можно рассматривать, как своеобразный цикл. Рассмотрим её на примере следующей задачи: «Вывести все числа массива»
Код с использованием рекурсии:
В результате мы получим следующее:
Условие if позволяет нам заходить в внутрь до тех пор, пока наш список не пустой, т.е. в нем есть числа. Далее, видим код до вызова функции в условии выполняется сразу, а вот после в обратном порядке. Можно изобразить работу функции в виде лесенки, смотрим на рисунок 2.
При использовании рекурсии надо помнить о двух условиях:
1. Условие остановки рекурсии. Еще это называют базовым случаем, элементарным случаем. В нашей задачке выше это условие – пустой список
2. Условие приближения к элементарному случаю. У нас это извлечение по одному элементу из списка за каждый шаг рекурсии.
Внимательные заметили, что на каждом шаге рекурсии мы создаем одну и туже переменную number. Почему не возникает конфликта? Потому что наш компьютер воспринимает их как разные переменные. Возникает это из-за того, что рекурсия храниться в памяти компьютера в виде стэка.
т.е. все что создано на предыдущем шаге записывается в стэк, храниться в нем и как бы «стирается» из памяти, которой вы оперируете в данный момент. После достижения элементарного случая, выполняется код после рекурсии, и переменная освобождает память, извлекается предыдущий шаг из стэка вместе с созданной ранее переменной. Так до тех пор, пока из стэка не будут извлечены все шаги.
Рекурсия полезный прием, помогающий упростить понимание и написание многих алгоритмов. Тем не менее её использования можно избежать заменой на стэк, но это сложнее для реализации.
К минусам можно отнести то что рекурсия требует дополнительной памяти и имеет ограничения в глубине рекурсии. Для python по умолчанию глубина равна 1000, но это значение можно изменять.
И наверное последний вопрос в этой статье: Зачем нам рекурсия прямо сейчас? Рекурсия позволяет очень просто и быстро написать алгоритм сортировки слиянием. Его разберем в следующей статье.