Что такое рекурсия и как ее использовать?

Дядя Влад

Рекурсия – это забавная концепция программирования, но может быть немного сложной для изучения. Рекурсия просто означает что-то, что повторяется. Если вы хотите увидеть нахальный пример рекурсии, попробуйте поискать рекурсию в Google. Вы найдете пасхальное яйцо, в котором предложения результатов поиска рекурсивны. С другой стороны, если вы хотите научиться кодировать рекурсивную функцию, читайте дальше!

Что такое рекурсивная функция?

Рекурсивная функция – это функция, которая вызывает сама себя. По сути, вы создаете цикл с функцией. Как вы понимаете, написать эти функции может быть непросто. Вы не хотите, чтобы ваш код работал вечно.

Подобно циклу, рекурсивная функция будет управляться условием. Как только условие выполнено, функция перестает вызывать саму себя, что останавливает цикл. Вот как вы можете создать функцию, которая вызывает сама себя, не выполняя ее вечно.

Хотя рекурсивная функция действует как цикл, компьютер выполняет ее иначе. Итак, некоторые алгоритмы более эффективны в цикле, а другие выигрывают от рекурсивной функции. Но прежде чем мы рассмотрим, как использовать рекурсивную функцию, вам нужно знать, как ее написать.

Как написать рекурсивную функцию

Все рекурсивные функции имеют одинаковую базовую структуру:

 FUNCTION name
 IF condition THEN
 RETURN result
 ELSE
 CALL FUNCTION name
 END FUNCTION

Приведенный выше пример написан в псевдокоде. Он описывает структуру функции, которая может быть применена к любому языку. Для простоты в этой статье мы сконцентрируемся на Python.

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

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

Связанный: Что такое функция в программировании?

Пример рекурсивной функции в Python

Будет намного легче понять, как работает рекурсия, когда вы увидите ее в действии. Чтобы продемонстрировать это, давайте напишем рекурсивную функцию, которая возвращает факториал числа.

Факториалы возвращают произведение числа и всех целых чисел перед ним. Например, факториал 5 равен 5 x 4 x 3 x 2 x 1 или 120.

 def factorialFunction(numberToMultiply):
 if numberToMultiply == 1 :
 return 1
 else :
 return numberToMultiply * factorialFunction(numberToMultiply - 1)

 result = factorialFunction(3)
 print(result)
 //Outputs: 6

Вышеупомянутая программа выдаст вам результат 6, который является факториалом числа 3. Поначалу это может немного сбивать с толку. Поможет, если мы пройдемся по программе шаг за шагом.

  1. Когда функция вызывается, numberToMultiply равно 3.
  2. Условие не выполняется, поэтому переходим к условию else .
  3. Наша функция возвращает 3 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
  4. Когда на этот раз вызывается функция, значение numberToMultiply равно 2.
  5. Условие не выполняется, поэтому переходим к условию else.
  6. Наша функция возвращает 2 *, но затем останавливается. Он должен вызвать себя, чтобы определить остальную часть возвращаемого значения.
  7. Функция вызывается снова. На этот раз значение numberToMultiply равно 1.
  8. Наше условие if выполнено. Функция возвращает 1.
  9. Функция из шага 6 теперь может возвращать 2 * 1 функции из шага 3.
  10. Функция на третьем шаге теперь может возвращать 3 * 2 * 1, что равно 6.

Рекурсия – сложная концепция. Может быть полезно думать об этом как о наложении одной функции поверх другой. Как только одна функция будет окончательно разрешена, она может отправить информацию обратно в стек, пока все функции не получат свой ответ.

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

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

Пример преобразования цикла в рекурсивную функцию

 print("Enter an even number:")
 i = int(input())
 while (i % 2) != 0 :
 print("That number is not even. Please enter a new number:")
 i = int(input())

Этот цикл также можно записать рекурсивно как:

 def recursiveFunction(number) :
 if (number % 2) == 0 :
 return number
 else:
 print("That number is not even. Please enter a new number:")
 recursiveFunction(int(input()))

 print("Enter and even number:")
 i = recursiveFunction(int(input()))

Первый шаг – определить, когда вы хотите, чтобы ваша функция остановилась. В этом случае мы хотим, чтобы он останавливался после ввода четного числа. В нашем примере число отслеживает ввод пользователя. Если они вводят четное число, мы возвращаем число. В противном случае мы продолжим запрашивать новый номер.

Чтобы настроить цикл, мы снова вызываем нашу функцию. Но на этот раз число, которое мы передаем следующей функции, – это новый номер, введенный пользователем. Следующий вызов функции проверит номер.

Это действительно плохая функция! Да, он проверяет, четное ли число, как и наш цикл, но неэффективно. Каждый раз, когда пользователь вводит нечетное число, функция сохраняется в памяти и вызывается новая функция. Если вы сделаете это достаточно много раз, у вас закончится память!

Связанный: Основные примеры Python, которые помогут вам быстро изучить

Реальный пример рекурсивной функции

Приведенные выше примеры были хорошими примерами того, когда не использовать рекурсию. Итак, где используется рекурсия? Хороший пример использования рекурсии – поиск в двоичном дереве.

Когда данные структурированы в виде двоичного дерева, вам придется пройти множество путей для поиска данных. В каждой точке дерева вы должны решить, хотите ли вы продолжить поиск справа или слева. Вы можете сохранить в переменной, какую часть дерева вы посетили, но рекурсивная функция, естественно, может отслеживать эту информацию.

Представьте, что мы ищем число шесть на дереве выше. Мы могли бы создать рекурсивную функцию, которая просматривает дерево слева направо. Алгоритм выглядел бы примерно так:

 FUNCTION searchTree(branchToSearch)
 IF find 6 OR end of tree THEN
 RETURN result
 ELSE
 PROCESS branch
 CALL FUNCTION searchTree(left)
 CALL FUNCTION searchTree(right)
 END FUNCTION

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

Алгоритм всегда будет сначала искать слева, насколько это возможно. как только он достигнет конца дерева, searchTree (слева) завершится и проверит правую сторону. Как только обе стороны проверены, поиск дублирует одну ветвь и продолжает проверку правой стороны.

Если бы алгоритмы просматривали все дерево, они бы делали это в следующем порядке:

2, 7, 2, 6, 5, 11, 5, 9 и 4

Посмотрите, сможете ли вы продолжить, используя приведенный выше псевдокод.

Обзор рекурсии

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

При написании рекурсивной функции начните с решения, как вы хотите выйти из функции. Затем определите, как настроить цикл. Определите, какую информацию нужно отправить при следующем вызове функции, а что нужно вернуть.

Лучший способ научиться рекурсии – это практиковать ее и учиться на своих ошибках. Посмотрите на свой старый код и поставьте перед собой задачу переписать циклы как рекурсивные функции. Скорее всего, это не сделает ваш код более эффективным, но это будет хорошей практикой.