Рекурсия на практике

Числа Фибоначчи

Последовательность Фибоначчи начинается с 0 и 1, а каждое следующее число — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13... Её определение само по себе рекурсивно: F(n) = F(n−1) + F(n−2), с двумя базовыми случаями F(0) = 0 и F(1) = 1.

Переворот строки рекурсией

Рекурсивно строкуТекстовое значение в кавычках: "привет". Неизменяема. По-английски string (str). можно перевернуть так: «последний символ + перевёрнутый остаток». База — пустая строка, которую переворачивать не нужно.

Разбор: reverse("abc") = "c" + reverse("ab") = "c" + "b" + reverse("a") = "cba". Срез s[:-1] отбрасывает последний символ, постепенно укорачивая строку до пустой.

Вернётся 15 (1+2+3+4+5). Когда элемент оказывается списком, функция вызывает себя для него — так рекурсия добирается до любой глубины вложенности. Это классический приём обхода «деревьев» из вложенных структур.

⚠️ Частые ошибки новичков

Ошибка. Шаг рекурсии не приближает к базовому случаю. Например, передавать в вызов то же самое значение. Запустите код — он зациклится и упадёт с RecursionError. Почините: уменьшайте аргументЗначение, которое передаётся функции при вызове. Внутри функции оно доступно как параметр., чтобы дойти до базы (n - 1).