Чтобы понять рекурсию, нужно сначала понять рекурсию.
~ Стивен Хокинг
- Я думаю, что рекурсия — один из самых полезных инструментов программирования, и он действительно дает мне суть оптимизированного и эффективного программирования.
Почему вы должны беспокоиться об этой статье?
- Я знаю, что есть много замечательных и информативных статей о рекурсии, но большинство из нас не доходит до конца.
- Это свежий взгляд студента (меня), который совсем недавно изучил этот мощный инструмент программирования.
- Но я почти уверен, что не буду из-за его функциональности и мощности 😎 В этой статье я попытаюсь максимально упростить рекурсию.
Определения
- Википедийное определение:
Recursion is the process of repeating items in a self-similar way
Это было действительно полезно, верно?
Чтобы по-настоящему понять рекурсию, подумайте о длинной очереди, в которой вы стоите в определенной позиции, и вы не знаете, в какой она позиции, поэтому вы спрашиваете человека перед вами, но поскольку очередь длинная, этот человек также не знает свою позицию, поэтому он/она делает то же самое (спрашивает человека перед ним), это продолжается до тех пор, пока здесь не спросят человека, стоящего первым в очереди, он знает свою позицию, которая находится первой, поэтому этот человек говорит это позицию второму, затем второй говорит третьему, и так продолжается, и вы получаете свой ответ (ваша позиция в очереди)
Итак, давайте разберемся, чем заканчивается эта длинная история
Алгоритмически
- Здесь вы используете технику «разделяй и властвуй» или «убавляй и властвуй», разбивая свою сложную проблему (определение своего положения в очереди) на более мелкие (задавая вопросы каждому следующему человеку).
- И первый человек в очереди на самом деле является
base case
, где рекурсия останавливается и возвращает ответ на вопрос, заданный 2-м человеком, который возвращает ответ для 3-го, и это продолжается до тех пор, пока ответ не будет получен.
Семантически
- То, что вы делаете, вызывает функцию внутри себя
- С базовым случаем, чтобы остановить рекурсию, потому что мы не хотим бесконечной рекурсии.
ПРИМЕРЫ
1. Умножение
- Представьте, что вы умножаете a на b, но у вас есть только оператор сложения, поэтому мы добавляем a к самому себе b раз.
- Таким образом, простое итеративное решение будет следующим:
def mut_iter( a , b ) i = 0 while b > 0 : b -= 1 i += a return i
- Но теперь подумайте об этом рекурсивно, т.е.
a + a + ........ + a
}---› этоa
b раз, а также +a + .........+ a
}---› это + [a
( b-1 ) раз]
Рекурсивный шаг:
- Это сведение проблемы к более простой версии самой себя
- здесь a + a*(b-1) — рекурсивный шаг
Базовый вариант :
- Это самый простой случай, который можно решить напрямую
- здесь b = 1 — простейший случай, который можно решить напрямую, вернув ответ в виде
Рекурсивное решение можно записать следующим образом:
def mult ( a, b ):
if b == 1 :
return a
else:
return a + mult ( a, b-1 )
https://twitter.com/kevinnaughtonjr/status/1568293112979537922?s=21&t=3Ai1ayi73e32bgbt8ZsECw
2. Факториал
- Нахождение факториала — один из наиболее распространенных примеров рекурсии.
- Итак, что мы знаем о факториале, чтобы использовать его в качестве базового случая: n = 1 —> n! = 1
- Поэтому рекурсивное решение будет выглядеть следующим образом:
def fact(n): if n == 1: return 1 else: n * fact ( n-1 )
- Поскольку мы вызываем функцию внутри себя, она создает локальную область видимости для каждого рекурсивного шага и возвращает значение при достижении базового случая.
- Эффективность рекурсии из-за создания временной локальной области видимости зависит от того, может ли она быть эффективной в одних языках и нет в других.
📌 Примечание. Если вы не знакомы с концепцией области видимости, вы можете обратиться к некоторым статьям ниже:
saltycrane.com/blog/2008/01/python-переменная..
realpython.com/python-scope-legb-rule/#unde..
- Давайте посмотрим на итеративное решение для того же самого:
def fact_itr (n):
prod = 1
for i in range(1,n+1):
prod *= i
return prod
Or
def fact_itr (n): prod = 1 for i in range(1,n+1): prod *= i return prod
- Рекурсии могут быть эффективными с точки зрения программиста, а иногда могут быть неэффективными с точки зрения компьютера.
Некоторые хорошие примеры, которые вы можете проверить:
- Башни Ханоя
Программа для алгоритма «Ханойская башня — GeeksforGeeksПортал компьютерных наук для гиков. Он содержит хорошо написанные, хорошо продуманные и хорошо объясненные статьи по информатике и программированию, викторины и … www.geeksforgeeks.org»
- Числа Фибоначчи (отличный пример с несколькими базовыми вариантами)
- Поиск палиндромов
- Нахождение наибольшего общего делителя (НОД)
📌 Все эти примеры также могут быть написаны итеративно, что может быть забавным заданием, а некоторые из этих примеров также заставят вас осознать силу рекурсии😎, поэтому попробуйте сделать их самостоятельно.