Помните анкету-знакомство? Если бы программисты были маленькими девочками и составляли такие опросники, то обязательно был бы вопрос о любимом языке программирования. Почему-то мне часто хочется сказать, что это LISP.
Существует несколько "стилей мышления" при написании программ. Ученые называют их парадигмами программирования. В коммерческой разработке чаще всего используется объектно-ориентированный подход. К нему относятся такие популярные языки, как Java, Python, C++, C# и т. д. А вот Lisp принадлежит к функциональной парадигме. Слышала мнение, что именно этот стиль мышления ближе к естественной работе мозга. Иногда преподаватели замечают, как студенты, не справившиеся с Cи, Python или Pascal, вдруг очень легко начинают писать на Lisp. Утверждение смелое, ничем не подтвержденное, но интересное.
Про парадигмы и их отличия поговорим как-нибудь отдельно, а сегодня о рекурсии! Такая долгая подводка была нужна потому, что рекурсия — единственный способ сделать цикл в функциональном программировании. При работе с Lisp я опробовала ее вдоль и поперек. Первый раз, когда написала рекурсивный алгоритм, чувствовала себя сверхчеловеком. Сегодня понимаю, что ничего сложного в этом нет, особенно если задача подходит под такой стиль мышления.
Рекурсия — это когда объект является частью самого себя. Звучит странно, но таких примеров много в обычном мире:
❄Снежинка, например. Её форма состоит из повторяющихся фигур, похожих на всю снежинку целиком. Научное название такому - фрактал.
🪞Мистический пример: гадание в зеркальном коридоре. От предсказывания будущего воздержимся, но представить явление легко. Отражения повторяются друг в друге, образуя бесконечную рекурсию.
🥦В мире растений есть гибрид цветной капусты и брокколи, называемый Амфора F1, который тоже повторяет рекурсивные паттерны. Посмотрите, какая красота! Мама, это тебе идея для огорода!
В программировании рекурсия встречается в двух плоскостях:
1⃣ Рекурсивный вызов функции. Это когда функция вызывает сама себя. Чтобы избежать "зеркального коридора", такая функция должна иметь терминальное условие, прекращающее повторение. Цветная капуста ведь тоже не бесконечна — меньше размера атома вы пучок не сделаете. Мне было проще писать рекурсивные функции, начиная как раз с описания терминальных условий.
2⃣ Рекурсивные структуры данных. Если когда-то создавали списки или деревья с нуля, то вы с этим знакомы. Узел простейшего однонаправленного списка — это значение и указатель на следующий элемент, то есть на такой же узел. Вот вам и рекурсия.
Говорят, что рекурсивные структуры естественнее обрабатывать рекурсивными алгоритмами. Идея хорошая, но у рекурсии, в отличие от цикла, есть ограничения. Они зависят от глубины стека вызовов, структуры кода функции и умения оптимизировать хвостовую рекурсию. Помню, Саша на первых курсах университета пытался написать численный метод через рекурсию. Не хватило размера стека для нужного количества итераций. Почему он выбрал рекурсию? Может, идея о естественности этого подхода действительно имеет смысл?
Давайте напишем функцию для вычисления факториала.
Формула: N! = N × ... × 3 × 2 × 1, или N! = N ×(N-1)!. Видете рекурсию? Мы считаем факториал через факториал.
⬛ Начнем с терминального условия: factorial(1) = 1
⬛ Основная логика: factorial(N) = N × factorial(N - 1)
Перепишем это на LISP:
(defun factorial(n)
(cond
((= n 1) 1)
(t (* n (factorial (- n 1))))
)
)
Логика определения и кода идентична. Красота!
Онлайн интерпретатор Lisp если хотите поиграться https://www.tutorialspoint.com/compilers/online-lisp-compiler.htm
#it #бабанюра_программирует