Чтобы легко понять что такое рекурсия давайте обратимся к примерам. Первым примером для нас послужат числа Фибоначчи - последовательность чисел, в которой первые 2 элемента равны 1, а остальные равны сумме двух предыдущих. Мы можем записать формулу i - го члена последовательности Фибоначчи следующим образом:
Подобная формула называется рекуррентной, так как задает члены последовательности, через другие ее члены и некоторую базу, коей являются первые 2 члена.
Обратимся к другому примеру - факториал числа. Факториалом целого неотрицательного числа n называется произведение всех натуральных чисел от 1 до n. Давайте попробуем обратить эту формулу в рекуррентную. Для начала определимся с базой, мы знаем что 1! = 1. Этой базы нам хватит, помимо этого нам нужно правило для получения факториалов остальных чисел. В принципе из определения очевидно, что n! = (n-1)! * n. Получаем следующую рекуррентную формулу:
Я думаю, что мы достаточно разобрались с рекурсией, пришло время воплотить ее в код. На языке C++ функция вычисления факториала числа, будет выглядеть следующим образом:
Для вычисления чисел Фибоначчи функция так же выглядит довольно просто:
Вот только при попытке вычислить например 50-ое число при помощи такой функции ваш компьютер призадумается на неопределенный срок, различные методы оптимизации подобных вычислений мы с вами разберем в будущих статьях.
Рекурсию мы часто можем встретить в повседневной жизни. Многие дизайнеры пытаются заигрывать с ней в своих творениях
Так же яркой иллюстрацией рекурсии являются фракталы - геометрические фигуры, обладающие самоподобием.
Рекурсию можно наблюдать у стримеров, когда они разворачивают окно стриминговой программы с предпросмотром их экрана:
В программировании рекурсия - необходимая вещь, ведь она делает запись многих алгоритмов намного проще, но стоит помнить, что рекурсия замедляет работу программы в сравнение с циклом, так же стоит помнить, что любую рекурсию можно циклом заменить, однако в таком случае в коде появятся нагромождения и уменьшится его читабельность. Программистам стоит с умом использовать рекурсию.
В следующей статье поговорим про более продвинутые рекурсивные алгоритмы, а так же разберемся со способами избавления от рекурсии и замены ее циклами.
На этом статья подходит к концу, не забудьте подписаться на канал, дабы не пропускать новые статьи.
