Чтобы понять рекурсию, нужно сначала понять рекурсию.
~ Стивен Хокинг

  • Я думаю, что рекурсия — один из самых полезных инструментов программирования, и он действительно дает мне суть оптимизированного и эффективного программирования.

Почему вы должны беспокоиться об этой статье?

  • Я знаю, что есть много замечательных и информативных статей о рекурсии, но большинство из нас не доходит до конца.
  • Это свежий взгляд студента (меня), который совсем недавно изучил этот мощный инструмент программирования.

  • Но я почти уверен, что не буду из-за его функциональности и мощности 😎 В этой статье я попытаюсь максимально упростить рекурсию.

Определения

  • Википедийное определение:

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 }---› это ab раз, а также +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
  • Рекурсии могут быть эффективными с точки зрения программиста, а иногда могут быть неэффективными с точки зрения компьютера.

Некоторые хорошие примеры, которые вы можете проверить:

  1. Башни Ханоя

Программа для алгоритма «Ханойская башня — GeeksforGeeksПортал компьютерных наук для гиков. Он содержит хорошо написанные, хорошо продуманные и хорошо объясненные статьи по информатике и программированию, викторины и … www.geeksforgeeks.org»

  1. Числа Фибоначчи (отличный пример с несколькими базовыми вариантами)

Программа для чисел Фибоначчи — GeeksforGeeksЧисла Фибоначчи — это числа в следующей целочисленной последовательности. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,….Программа для чисел Фибоначчи…www.geeksforgeeks.org

  1. Поиск палиндромов

Рекурсивная функция проверки палиндромности строки — GeeksforGeeksИнформатический портал для гиков. Он содержит хорошо написанные, хорошо продуманные и хорошо объясненные статьи по информатике и программированию, викторины и … www.geeksforgeeks.org

  1. Нахождение наибольшего общего делителя (НОД)

gcd() в Python — GeeksforGeeksПортал компьютерных наук для гиков. Он содержит хорошо написанные, хорошо продуманные и хорошо объясненные статьи по информатике и программированию, викторины и … www.geeksforgeeks.org

📌 Все эти примеры также могут быть написаны итеративно, что может быть забавным заданием, а некоторые из этих примеров также заставят вас осознать силу рекурсии😎, поэтому попробуйте сделать их самостоятельно.