Рекурсивный алгоритм
Одним из широко используемых алгоритмов является рекурсивный алгоритм. Он используется не только в информатике, но и в реальной жизни.
Рекурсивный — это процесс, в котором вы делите задачу на подзадачи, и решение каждой задачи зависит от меньшей версии задачи.
В программировании рекурсия используется для повторного вызова функции до тех пор, пока не будет выполнено условие завершения. Но каждый раз, когда функция вызывает сама себя, задача разбивается на более мелкие задачи.
Приложение
Например, давайте посмотрим на факториал числа.
Пусть «n» будет вещественным числом, так что.. n! Является факториалом n.
Мы можем сказать, что:
n! = n*(n-1)!
Мы можем разделить его еще меньше, чтобы быть
n! = n*(n-1)*(n-2)!
Его можно разделить еще дальше:
n! = n*(n-1)*(n-2)*(n-3)*…..3*2*1
Здесь мы видим, что можем разделить n! к меньшему значению n*(n-1)!
Заметим также, что найти ответ n! Нам нужно найти ответ на n*(n-1)! А для этого нам нужно найти решение (n-1)! И умножить на n. Чтобы найти значение (n-1)! мы можем разделить (n-1)! К меньшему значению, которое будет (n-1)*(n-2)! Чтобы найти значение (n-1)*(n-2)! Нам нужно найти значение (n-2)! Чтобы найти его, нам нужно упростить (n-2)! в меньшее значение, а затем умножьте его на (n-1), что будет (n-2)*(n-3)! Это будет продолжаться до тех пор, пока вы не получите значение «1», которое нельзя разделить на меньшее значение. Итак, каждое значение выражения зависит от значения перед ним. Так как н! Зависит от значения n*(n-1)! И (н-1)! Зависит от значения (n-1)*(n-2)!… и т.д.
Рекурсивный алгоритм содержит базовое условие, которое завершает операцию, если оно выполняется. В случае факториала базовое условие равно «1», потому что алгоритм остановится, как только факториал достигнет «1».
Мы можем написать код факториала на Python следующим образом:
Последнее утверждение «вернуть n*fact(n-1)» говорит, что если базовое условие не выполняется, то умножить «n» на факт(n-1).
fact(n-1) снова вызывает функцию «fact», но на этот раз со значением (n-1). Факт (n-1) говорит, что если базовое условие не выполняется, то умножьте (n-1) на и функцию «факт (n-2)». Это будет продолжаться до тех пор, пока «n» не достигнет 1. Когда n==1, он вернет 1.
Как только он возвращает 1, он фактически вызывает функцию факта (2–1), поэтому «1» будет решением факта (2–1). Изначально было:
2*fact(2–1) и мы сказали, что fact(2–1) равен 1, поэтому факт(2–1) заменится на 1 . Теперь у нас есть 2 * 1 = 2
2*1 появился в результате вызова функции fact(3–1), которая исходно пришла из
3*факт(3–1), поэтому вместо факта(3–1) мы поставим 3*2*1 и так далее…
Башни Ханоя
Еще одним приложением на рекурсии является игра «Ханойские башни».
В этой игре у нас есть кольца, которые надеваются друг на друга от самого маленького до самого большого. Требуется переместить кольца из башни, в которой они находятся (1-я башня), в 3-ю башню. В условиях, когда вы можете перемещать только одно кольцо за раз и вы не можете положить большое кольцо поверх маленького кольца
Чтобы достичь цели (C), нам нужно переместить самую большую фигуру (красную) из A в C. Для этого нам нужно переместить каждую фигуру над самой большой фигурой в середину (B), чтобы красное кольцо могло переместитесь в C. Затем мы переместим кольца из (B) в (C).
Мы разделили задачу на меньшую задачу, которая включает в себя перемещение трех частей, а затем одну часть, а не все четыре части одновременно. Теперь у нас есть другая проблема, нам нужно положить зеленое кольцо поверх красного кольца. Таким образом, мы должны переместить фиолетовое и синее кольца из B в A, а затем переместить зеленое кольцо из B в C. Это разделило проблему на меньшую задачу, перемещая 2 кольца и 1 кольцо, а не 3 кольца одновременно.
Теперь нам нужно переместить фиолетовое кольцо из A в C. Для этого нам нужно переместить синее кольцо из A в B. Итак.
После перемещения фиолетового кольца мы переместим синее кольцо из B в C.
Вот как мы решаем Ханойскую башню с помощью рекурсии.
