Рекурсия: функция вызывает сама себя

Представь матрёшку. Тебе нужно найти самую маленькую куклу внутри. Инструкция короткая: «Открой матрёшку. Если внутри пусто, то эта кукла и есть самая маленькая. Если внутри есть кукла, сделай с ней то же самое». Заметь: инструкция ссылается сама на себя, но каждый раз кукла меньше, и рано или поздно ты дойдёшь до цельной малышки, которая не открывается.

В программировании так тоже можно: функция может вызывать саму себя. Сегодня разберёмся, как это работает, почему программа при этом не зависает навсегда (а иногда всё-таки ломается) и решим задачи, которые таким способом пишутся в 4–5 строк: степень числа, числа Фибоначчи и даже разворот последовательности без списков.