Рекурсия — одна из фундаментальных концепций информатики, она важна как для программистов, так и для специалистов по обработке данных. Мало того, что многие алгоритмы сортировки и поиска рекурсивны, но каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает, что рекурсия является ключевой концепцией, которую необходимо пересмотреть перед любым собеседованием по кодированию.
Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.
- Что такое рекурсия?
- Прямая против косвенной рекурсии
- Плюсы и минусы рекурсии в Python
- Рекурсия в Python
- Рекурсия Python с числами
- Последовательность Фибоначчи
- Сумма от 1 до n
- Рекурсия Python со строками и массивами
- Удалить пробелы из строки
- Инвертировать массив
- Рекурсия Python со структурами данных
- Обратный связанный список
- Распечатать все листовые узлы двоичного дерева слева направо
Что такое рекурсия?
Рекурсия — это концепция в информатике, когда функция вызывает саму себя и выполняет цикл до тех пор, пока не достигнет желаемого конечного условия. Он основан на математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.
Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние было достигнуто, и рекурсивный случай, когда желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг.
Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Поэтому рекурсивные структуры полезны, когда вы можете решить более серьёзную проблему (базовый случай), выполнив повторяющиеся подзадачи (рекурсивный случай), которые постепенно перемещают программу к базовому случаю.
Это приводит к поведению, аналогичному циклам for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как for циклы выполняются заданное количество раз, а while циклы выполняются до тех пор, пока условие больше не будет выполняться.
Другими словами, рекурсия декларативна, потому что вы устанавливаете состояние, которого хотите достичь, а for/ while циклы являются итеративными, потому что вам нужно установить количество повторений.
def RecursiveFunction() :# Base Caseif <baseCaseCondition> : #sets target state<return some base case value># Recursive Caseelse :<return(recursive call and any other task)>
Рекурсивные решения лучше всего подходят, когда проблема имеет чёткие подзадачи, которые необходимо повторить, и если вы не уверены, сколько раз вам нужно будет выполнить цикл с итеративным решением.
Например, если вы хотите создать программу-функцию факториала, которая находит факториал неизвестного числа.
def factorial(n):if n==0:return 1return n*factorial(n-1)num = 5print(factorial(num))
Прямая против косвенной рекурсии
До сих пор мы обсуждали только прямую рекурсию, когда рекурсивная функция явно вызывает себя на своём рекурсивном шаге. Существует также косвенная рекурсия, когда рекурсивный вызов удаляется из функции, но всё ещё выполняется в результате исходного рекурсивного шага.
Например, functionAзвонки functionB, которые потом звонят function Aснова.
- Прямой
def function1(p1, p2, …, pn) :# Some code herefunction1(p1, p2, …, pn)# Some code here
- Косвенный
def function1(p1, p2, …, pn) :# Some code herefunction2(p1, p2, …, pn)# Some code heredef function2(p1, p2, …, pn) :# Some code herefunction1(p1, p2, …, pn)# Some code here
Плюсы и минусы рекурсии в Python
Все языки программирования поддерживают рекурсию, однако не все одинаково оптимизированы.
Итерация часто является предпочтительной в Python и считается более «питонической» из-за встроенных оптимизаций. Как правило, рекурсивные решения предпочтительнее итеративных решений при больших вычислениях, поскольку рекурсия часто приводит к меньшему количеству кода и более высокой производительности при масштабировании.
Плюсы
- Быстрее при оптимизации : если вы включите оптимизацию рекурсии, такую как конечная рекурсия и мемоизация, рекурсивные подходы будут быстрее в Python.
- Меньше кода : рекурсивные решения более компактны, что означает, что вы можете писать рекурсивные решения быстрее и иметь меньше кода для проверки при отладке.
- Декларативность : многие разработчики считают логику объявления желаемого состояния более понятной, чем итерация, которая фокусируется на шагах, необходимых для достижения неустановленной цели.
- Эффективная сортировка и поиск : рекурсия особенно полезна для науки о данных Python, поскольку она является основой популярных алгоритмов сортировки, таких как сортировка слиянием.
Минусы
- Максимальная глубина рекурсии: Python имеет ограниченный стек вызовов, который поддерживает только 1000 вложенных шагов. Хотя это может показаться большим, это становится проблемой при работе с большими структурами, такими как списки и массивы. Это можно изменить по вашему усмотрению с помощью setrecursionlimit(1500).
- Поддерживается, не рекомендуется: Python допускает рекурсивные вызовы, но не включает многих встроенных оптимизаций. В отличие от итеративных оптимизаций, разработчики должны сами кодировать полностью рекурсивные улучшения.
- Использует больше памяти: каждый вызов сохраняет предыдущий шаг в стеке вызовов до завершения рекурсивного процесса. Это означает, что рекурсивные решения используют больше памяти, чем итерационные.
Я не добавил удобочитаемости ни в один из столбцов, поскольку некоторые разработчики считают рекурсию более понятной, в то время как другие находят вложенное поведение запутанным. В конечном счёте, это индивидуально для каждой проблемы и разработчика.
Рекурсия в Python
Теперь давайте более подробно рассмотрим рекурсивные функции в Python.
Ниже приведён пример программы, которая рекурсивно печатает шаблон: 10 5 0 5 10.
def printPattern(targetNumber) :# Base Caseif (targetNumber <= 0) :print(targetNumber)return# Recursive Caseprint(targetNumber)printPattern(targetNumber — 5)print(targetNumber)# Driver Programn = 10printPattern(n)
Мы хотим напечатать каждое число дважды, за исключением того, 0что оно печатается только один раз в середине. Это позволяет нам узнать, что if (targetNumber <= 0)это наш базовый вариант.
Таким образом, наш рекурсивный случай — это строки 7–9.
В строке 8 вы можете увидеть рекурсивный вызов printPattern(targetNumber — 5), который переводит нашу программу на следующий рекурсивный шаг.
Строка 9 печатает финал 10и запускается только один раз, как и после рекурсивного вызова.
Помните, что в рекурсивном цикле повторяется только поведение до рекурсивного вызова.
Взгляните на эту блок-схему программы, чтобы увидеть, как связаны шаги программы:
Давайте посмотрим на стек вызовов по мере выполнения этой программы:
Теперь, когда мы разобрали эту рекурсивную программу, давайте рассмотрим некоторые применения рекурсии.
Рекурсия Python с числами
Последовательность Фибоначчи
Сначала мы рассмотрим классический пример рекурсии: последовательность Фибоначчи. Эта программа берёт заданное число и возвращает его числа Фибоначчи.
def recur_fibo(n):# Base Caseif n <= 1:return nelse:# Recursive Casereturn(recur_fibo(n-1) + recur_fibo(n-2))# Driver Codenum = 10print (recur_fibo(num))
Вы можете увидеть наш базовый вариант в строке 2 if n >= 1,. Если это не выполняется, мы переходим к рекурсивному случаю в строке 5, который содержит два рекурсивных вызова.
Каждый раз, когда цикл повторяется, nзначение опускается, что означает, что в конце концов наш базовый случай станет верным.
Сумма от 1 до n
Теперь посмотрим, как с помощью рекурсии суммировать все числа от 1 до данного числа. Эта программа принимает на вход положительное целое число и возвращает единственную распечатку суммы всех чисел от 1 до целого.
def sumTill(targetNumber) :# Base Caseif targetNumber == 1 :return targetNumber# Recursive Caseelse :return targetNumber + sumTill(targetNumber — 1)# Driver CodetargetNumber = 5print(sumTill(targetNumber))
Наша программа начинается с заданного числа и на каждом рекурсивном шаге добавляет цифру на единицу ниже, пока не достигнет 1.
Базовый вариант находится в строке 3 if targetNumber ==1,. В рекурсивном случае текущее значение targetNumberthen вызовов sumTill()складывается со значением на 1 меньше.
Рекурсия Python со строками и массивами
Рекурсия также полезна со строками или массивами. Во многих рекурсивных вопросах собеседования вам будет предложено преобразовать строки или массивы, пока все они не будут соответствовать определённым критериям.
Удалить пробелы из строки
В этом упражнении мы создадим программу, которая принимает заданную строку и возвращает новую строку без пробелов или /t символов табуляции ( ). Например, Hello World стал бы HelloWorld.
def remove(string):# Base Caseif not string:return «»# Recursive Caseif string[0] == «\t» or string[0] == » «:return remove(string[1:])else:return string[0] + remove(string[1:])# Driver Codeprint(remove(«Hello\tWorld»))
Удаление вкладок из пустой строки «просто вернёт пустую строку». Следовательно, наш базовый случай будет, когда наша исходная строка пуста (строка 3).
Для рекурсивного случая в строках 7-10 мы проверяем, является ли текущий элемент «\t»или » «:
- Если текущий элемент — «\t»или » «мы отбрасываем его и вызываем другой экземпляр функции после удаления этого элемента.
- Если текущий элемент не является «\t»или » «, мы добавляем его к выходной строке и вызываем другой экземпляр функции после удаления этого элемента.
Инвертировать массив
Теперь мы создадим рекурсивную программу, которая принимает данный массив и возвращает тот же массив с элементами в обратном порядке. Например, 1, 2, 3, 4стал бы 4, 3, 2, 1.
def reverse(array):# Base case1if len(array) == 0: # If we encounter an empty array, simply return an empty arrayreturn []# Base case2elif len(array) == 1 : # Inverting an array of size 1 returns the same arrayreturn array# Recursive casereturn [array[len(array) — 1]] + reverse(array[:len(array) — 1])# The first part is storing the last element to be appended later# The second part is calling another instance of the same function with the last element removed# Driver Codearray = [1, 2, 3, 4]print(reverse(array))
Для этого решения мы создадим временную переменную, которая сохраняет последний элемент переданного массива на каждом рекурсивном шаге. В конце концов, эти значения будут использоваться для повторного заполнения массива в обратном порядке, потому что вложенные рекурсивные функции выполняются в первую очередь.
Базовые случаи этой проблемы — это когда в массиве содержится 0 или 1 элемент, потому что инвертирование этих массивов вернёт тот же массив.
Рекурсия Python со структурами данных
Наконец, давайте посмотрим, как рекурсивные функции могут использоваться в структурах данных, таких как связанные списки и двоичные деревья.
Обратный связанный список
Переворачивание связного списка аналогично переворачиванию массива, но немного сложнее. Эта программа примет связанный список и вернёт тот же связанный список с узлами в обратном порядке.
Например, связанный список 3, 4, 7, 11будет иметь возвращаемое значение 11, 7, 4, 3.
- main.py
# mainimport linkedList as ldef helperFunction(myLinkedList, current, previous) : # This function reverses the linked list recursively# Base caseif current.next is None :myLinkedList.head = currentcurrent.next = previousreturnnext = current.nextcurrent.next = previous# Recursive casehelperFunction(myLinkedList, next, current)def reverse(myLinkedList):# Check if the head node of the linked list is null or notif myLinkedList.head is None:return# Call the helper function —> main recursive functionhelperFunction(myLinkedList, myLinkedList.head, None)# Driver CodemyLinkedList = l.LinkedList()myLinkedList.append(3)myLinkedList.append(4)myLinkedList.append(7)myLinkedList.append(11)print(«Original Linked List»)myLinkedList.printList()reverse(myLinkedList)print(«\nReversed Linked List»)myLinkedList.printList()
- node.py
# node.pyclass Node:def __init__(self, data):self.data = dataself.next = None
- connectedList.py
# linkedList.pyimport node as nclass LinkedList:def __init__(self) :self.head = Nonedef append(self, new_data):new_node = n.Node(new_data)if self.head is None : # If head node is nullself.head = new_nodereturnlast = self.headwhile (last.next):last = last.nextlast.next = new_node # add new node to end of listdef printList(self):temp = self.headwhile(temp):print(temp.data)temp = temp.next
В приведённом выше фрагменте кода мы передаём наш связанный список myLinkedList в функцию reverse(). Эта функция проверяет, является ли заголовок связанного списка null. Если головной узел не равен нулю, мы вызываем helperFunction(). Эта функция является рекурсивной, и именно здесь происходит обращение связанного списка.
В этом helperFunction() узлы меняются местами с помощью следующих операторов:
next = current.next # The original next node of the current node is saved current.next = previous # The next of the current node is updated
После этого изменения мы снова рекурсивно вызываем функцию:
# Recursive case helperFunction(myLinkedList, next, current) # The current node in the next recursive call will be the "next" node that we saved. # The previous node will be the parent function's current node
Базовый случай для этой проблемы — когда мы достигаем конца связанного списка. Здесь будет next узел current узла None. Мы сделаем этот последний узел заголовком связанного списка, обновим его положение и return.
Распечатать все листовые узлы двоичного дерева слева направо
Этот вопрос немного сложен, но именно такой вопрос вы встретите на собеседовании по программированию на Python.
Мы создадим программу, которая печатает все листовые узлы в том виде, в каком они появляются слева направо на древовидной диаграмме. Это дерево, которое мы будем использовать.
Правильное решение для этого дерева 4 6 7 9 10.
Напоминание: конечные узлы — это узлы, у которых нет дочерних узлов, и поэтому они заканчивают ветвь поддерева.
- main.py
# Function to print leaf# nodes from left to rightdef printLeafNodes(root: Node) -> None:# If node is null, returnif (not root):return# If node is leaf node,# print its dataif (not root.left andnot root.right):print(root.data,end = » «)return# If left child exists,# check for leaf recursivelyif root.left:printLeafNodes(root.left)# If right child exists,# check for leaf recursivelyif root.right:printLeafNodes(root.right)# Driver Codeif __name__ == «__main__»:# Creates binary tree shown in# above diagramroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.right.left = Node(5)root.right.right = Node(8)root.right.left.left = Node(6)root.right.left.right = Node(7)root.right.right.left = Node(9)root.right.right.right = Node(10)# print leaf nodes of the given treeprintLeafNodes(root)
- node.py
# Binary tree nodeclass Node:def __init__(self, data):self.data = dataself.left = Noneself.right = None
Эта программа берёт корневой узел и печатает все листовые узлы слева направо. Наш базовый случай: либо 1) нет оставшихся узлов, либо 2) нет оставшихся листовых узлов.
Программа отслеживает соединения каждого дочернего элемента каждый раз, уходя влево, пока не найдёт листовой узел. Программа печатает это значение, а затем повторяет эту подзадачу для другого пути узлов.
В конце концов, функция вернётся, и все листовые узлы будут напечатаны слева направо.