Лучшие мемы

Что такое рекурсия и кто её придумал? Рекурсия — это когда функция (или процесс) зовёт сама себя. Как будто ты смотришь в зеркало, а в нём ещё одно зеркало, и ещё, и ещё — и всё повторяется по одному и тому же сценарию.Самый простой пример — факториал числа. Допустим, надо посчитать факториал 5 (это 5!). Логика такая:5! = 5 × 4!4! = 4 × 3!3! = 3 × 2!2! = 2 × 1!А 1! — это уже база, это просто 1.И вот от этой единицы всё обратно собирается: 2 × 1 = 2, потом 3 × 2 = 6, и так до 120. То есть функция каждый раз просит себя же посчитать чуть поменьше, пока не дойдёт до простого случая, который уже знает.Кто придумал? Тут нет одного «изобретателя» с патентом. Сама идея крутилась в математике веками. Например, древние греки использовали похожие приёмы, когда строили бесконечные ряды или определяли числа через предыдущие (как в последовательности Фибоначчи).А в программировании рекурсию как нормальный рабочий инструмент начали активно использовать в середине XX века, когда появились языки вроде Lisp (его придумал Джон Маккарти в 1958 году). В Lisp рекурсия вообще была главным способом делать циклы — там без неё никуда.Ещё важный факт: математическая база для рекурсии была заложена в работах Курта Гёделя и других логиков в 1930-х годах — они формализовали, как можно определять функции через самих себя.Пару фактов:У любой нормальной рекурсии должна быть «база» — условие, когда она перестаёт себя звать, иначе будет бесконечный цикл и программа упадёт.Рекурсия делает код короче и понятнее для некоторых задач (например, обход деревьев или папок на компьютере), но может жрать много памяти, потому что каждый «вызов себя» создаёт новый слой в стеке.