Рекурсия — одно из фундаментальных понятий информатики, одинаково важное для программистов и специалистов по данным. Мало того, что многие алгоритмы сортировки и поиска являются рекурсивными, каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это отмечает рекурсию как ключевую концепцию, которую необходимо пересмотреть перед любым собеседованием по программированию.
Сегодня мы поможем вам освежить ваши навыки рекурсивного программирования на Python и решить 6 практических задач, чтобы вы получили практический опыт.
Вот что мы сегодня рассмотрим:
- Что такое рекурсия?
- Рекурсия в Python
- Рекурсия Python с числами
- Рекурсия Python со строками и массивами
- Рекурсия Python со структурами данных
- Что изучать дальше
Что такое рекурсия?
Рекурсия — это понятие в информатике, когда функция вызывает сама себя и зацикливается, пока не достигнет желаемого конечного состояния. Он получен из математической концепции рекурсивных определений, которая определяет элементы в наборе с точки зрения других элементов в наборе.
Каждая рекурсивная реализация имеет базовый случай, когда желаемое состояние достигнуто, и рекурсивный случай, когда желаемое состояние не достигнуто и функция входит в еще один рекурсивный шаг.
Поведение в рекурсивном случае перед вызовом рекурсивной функции, внутренний самовызов, повторяется на каждом шаге. Таким образом, рекурсивные структуры полезны, когда вы можете решить более серьезную задачу (базовый случай) за счет выполнения повторяющихся подзадач (рекурсивный случай), которые постепенно перемещают программу к базовому варианту.
Это приводит к тому же поведению, что и циклы for или while, за исключением того, что рекурсия приближается к целевому условию, в то время как циклы for выполняются заданное количество раз, а циклы while выполняются до тех пор, пока условие больше не выполняется.
Другими словами, рекурсия является декларативной, поскольку вы устанавливаете состояние, которого хотите достичь, а циклы for/while являются итеративными, поскольку вы должны установить количество повторений.
Взгляните на разницу в синтаксисе между итеративным и рекурсивным подходами:
Рекурсивный:
def RecursiveFunction() :
# Base Case
if <baseCaseCondition> : #sets target state
<return some base case value>
# Recursive Case
else :
<return(recursive call and any other task)>
для:
arr = ["A", "B", "C"] for x in arr: #sets the number of iterations print(x) //output A B C
пока:
i = 1 while i < 6: #sets number of iterations print(i) i += 1 //output 1 2 3 4 5
Рекурсивные решения лучше всего подходят, когда у проблемы есть четкие подзадачи, которые необходимо повторять, и если вы не уверены, сколько раз вам потребуется выполнить цикл с итеративным решением.
Например, если вы хотите создать программу факториальной функции, которая находит факториал неизвестного числа.
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
num = 5
print(factorial(num))
//output
120
Прямая и косвенная рекурсия
До сих пор мы обсуждали только прямую рекурсию, когда рекурсивная функция явно вызывает саму себя на своем рекурсивном шаге. Существует также косвенная рекурсия, когда рекурсивный вызов удаляется из функции, но все еще выполняется в результате исходного рекурсивного шага.
Например, functionA вызывает functionB, который затем снова вызывает functionA.
Напрямую:
def function1(p1, p2, ..., pn) : # Some code here function1(p1, p2, ..., pn) # Some code here
Косвенный:
def function1(p1, p2, ..., pn) : # Some code here function2(p1, p2, ..., pn) # Some code here def function2(p1, p2, ..., pn) : # Some code here function1(p1, p2, ..., pn) # Some code here
Плюсы и минусы рекурсии в Python
Все языки программирования поддерживают рекурсию, однако не все одинаково оптимизированы.
Итерация часто предпочтительнее в Python и считается более «питоновской» из-за встроенных оптимизаций. Как правило, рекурсивные решения предпочтительнее итерационных решений для больших вычислений, поскольку рекурсия часто приводит к меньшему количеству кода и более высокой производительности в масштабе.
Плюсы:
- Быстрее при оптимизации. Если вы включаете оптимизацию рекурсии, такую как конечная рекурсия и мемоизация, рекурсивные подходы в Python работают быстрее.
- Меньше кода. Рекурсивные решения более компактны, а это означает, что вы можете писать рекурсивные решения быстрее и иметь меньше кода для проверки при отладке.
- Декларативный: многие разработчики считают логику объявления желаемого состояния более понятной, чем итерация, которая фокусируется на шагах, необходимых для достижения неустановленной цели.
- Эффективная сортировка и поиск: рекурсия особенно полезна для науки о данных Python, поскольку она является основой популярных алгоритмов сортировки, таких как сортировка слиянием.
Минусы:
- Максимальная глубина рекурсии: Python имеет ограниченный стек вызовов, который поддерживает только 1000 вложенных шагов. Хотя это может показаться большим, это становится проблемой при работе с большими структурами, такими как списки и массивы. Это можно переопределить на свой страх и риск с помощью
sys.setrecursionlimit(1500). - Поддерживается, но не рекомендуется: Python допускает рекурсивные вызовы, но не включает множество встроенных оптимизаций. В отличие от итеративной оптимизации, разработчики должны сами кодировать полностью рекурсивные улучшения.
- Использует больше памяти: каждый вызов сохраняет предыдущий шаг в стеке вызовов до завершения рекурсивного процесса. Это означает, что рекурсивные решения используют больше памяти, чем итеративные.
Мы не добавили удобочитаемости ни одному из столбцов, так как некоторым разработчикам проще понять рекурсию, а других смущает вложенное поведение. В конечном счете, это зависит от конкретной проблемы и разработчика.
Рекурсия в Python
Теперь давайте более подробно рассмотрим рекурсивные функции в Python.
Ниже приведен пример программы, которая рекурсивно печатает шаблон: 10 5 0 5 10.
def printPattern(targetNumber) :
# Base Case
if (targetNumber <= 0) :
print(targetNumber)
return
# Recursive Case
print(targetNumber)
printPattern(targetNumber - 5)
print(targetNumber)
# Driver Program
n = 10
printPattern(n)
//output
10
5
0
5
10
Мы хотим напечатать каждое число дважды, кроме 0, которое печатается только один раз в середине. Это дает нам понять, что if (targetNumber <= 0) является нашим базовым случаем.
Таким образом, наш рекурсивный случай — это строки 7–9.
В строке 8 вы можете увидеть рекурсивный вызов printPattern(targetNumber - 5), который переводит нашу программу на следующий рекурсивный шаг.
Строка 9 выводит последнее число 10 и запускается только один раз после рекурсивного вызова.
Помните, что в рекурсивном цикле повторяется только поведение до рекурсивного вызова.
Взгляните на эту блок-схему программы, чтобы увидеть, как соединяются шаги программы:
Давайте посмотрим на стек вызовов по мере того, как эта программа выполняет:
1.
2.
3.
4.
Теперь, когда мы разобрали эту рекурсивную программу, давайте рассмотрим некоторые приложения рекурсии.
Рекурсия Python с числами
Последовательность Фибоначчи
Сначала мы рассмотрим классический пример рекурсии: последовательность Фибоначчи. Эта программа берет заданное число и возвращает его числа Фибоначчи.
def recur_fibo(n):
# Base Case
if n <= 1:
return n
else:
# Recursive Case
return(recur_fibo(n-1) + recur_fibo(n-2))
# Driver Code
num = 10
print (recur_fibo(num))
//output
55
Вы можете увидеть наш базовый вариант в строке 2, if n >= 1. Если это не выполняется, мы переходим к рекурсивному случаю в строке 5, в которой есть два рекурсивных вызова.
Каждый раз, когда цикл повторяется, n понижается, а это означает, что наш базовый случай в конечном итоге станет истинным.
Сумма от 1 до n
Теперь мы увидим, как мы можем использовать рекурсию для суммирования всех чисел от 1 до заданного числа. Эта программа принимает в качестве входных данных положительное целое число и возвращает одну распечатку суммы всех чисел от 1 до целого числа.
def sumTill(targetNumber) :
# Base Case
if targetNumber == 1 :
return targetNumber
# Recursive Case
else :
return targetNumber + sumTill(targetNumber - 1)
# Driver Code
targetNumber = 5
print(sumTill(targetNumber))
//output
15
Наша программа начинается с заданного числа и добавляет число на единицу меньше на каждом рекурсивном шаге, пока не достигнет 1.
Базовый вариант находится в строке 3, if targetNumber ==1. Рекурсивный случай добавляет текущее значение targetNumber, а затем вызывает sumTill() со значением меньше на 1.
Рекурсия Python со строками и массивами
Рекурсия также полезна со строками или массивами. Во многих вопросах рекурсивного интервью вам будет предложено преобразовать строки или массивы, пока все они не будут соответствовать определенным критериям.
Удалить пробелы из строки
Для этого упражнения мы создадим программу, которая берет заданную строку и возвращает новую строку без каких-либо пробелов или символов табуляции (/t). Например, Hello World станет HelloWorld.
def remove(string):
# Base Case
if not string:
return ""
# Recursive Case
if string[0] == "\t" or string[0] == " ":
return remove(string[1:])
else:
return string[0] + remove(string[1:])
# Driver Code
print(remove("Hello\tWorld"))
//output
HelloWorld
Удаление табуляции из нулевой строки "" просто вернет нулевую строку "". Следовательно, нашим базовым случаем будет пустая исходная строка (строка 3).
Для рекурсивного случая в строках 7–10 мы проверяем, является ли текущий элемент "\t" или " ":
- Если текущий элемент
"\t"или" ", мы отбрасываем его и вызываем другой экземпляр функции после удаления этого элемента. - Если текущий элемент не
"\t"или" ", мы добавляем его к выходной строке и вызываем другой экземпляр функции после удаления этого элемента.
Инвертировать массив
Теперь мы создадим рекурсивную программу, которая берет заданный массив и возвращает тот же массив с элементами в обратном порядке. Например, 1, 2, 3, 4 станет 4, 3, 2, 1.
def reverse(array):
# Base case1
if len(array) == 0: # If we encounter an empty array, simply return an empty array
return []
# Base case2
elif len(array) == 1 : # Inverting an array of size 1 returns the same array
return array
# Recursive case
return [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 Code
array = [1, 2, 3, 4]
print(reverse(array))
//output
[4, 3, 2, 1]
Для этого решения мы создадим временную переменную, которая сохраняет конечный элемент из переданного массива на каждом шаге рекурсии. В конце концов, эти значения будут использоваться для повторного заполнения массива в обратном порядке, потому что вложенные рекурсивные функции сначала выполняют самые глубокие.
Базовые случаи этой проблемы — это когда массив имеет 0 или 1 элемент внутри, потому что инвертирование этих массивов вернет тот же массив.
Рекурсия Python со структурами данных
Наконец, давайте посмотрим, как можно использовать рекурсивные функции в таких структурах данных, как связанные списки и двоичные деревья.
Отменить связанный список
Обращение связанного списка похоже на обращение массива, но немного сложнее. Эта программа примет связанный список и вернет тот же связанный список с узлами в обратном порядке.
Например, связанный список 3, 4, 7, 11 будет иметь возвращаемое значение 11, 7, 4, 3.
main.py:
# main
import linkedList as l
def helperFunction(myLinkedList, current, previous) : # This function reverses the linked list recursively
# Base case
if current.next is None :
myLinkedList.head = current
current.next = previous
return
next = current.next
current.next = previous
# Recursive case
helperFunction(myLinkedList, next, current)
def reverse(myLinkedList):
# Check if the head node of the linked list is null or not
if myLinkedList.head is None:
return
# Call the helper function --> main recursive function
helperFunction(myLinkedList, myLinkedList.head, None)
# Driver Code
myLinkedList = 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.py
class Node:
def __init__(self, data):
self.data = data
self.next = None
linkedList.py:
# linkedList.py
import node as n
class LinkedList:
def __init__(self) :
self.head = None
def append(self, new_data):
new_node = n.Node(new_data)
if self.head is None : # If head node is null
self.head = new_node
return
last = self.head
while (last.next):
last = last.next
last.next = new_node # add new node to end of list
def printList(self):
temp = self.head
while(temp):
print(temp.data)
temp = temp.next
Вывод:
Original Linked List 3 4 7 11 Reversed Linked List 11 7
В приведенном выше фрагменте кода мы передаем связанный список 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 right
def printLeafNodes(root: Node) -> None:
# If node is null, return
if (not root):
return
# If node is leaf node,
# print its data
if (not root.left and
not root.right):
print(root.data,
end = " ")
return
# If left child exists,
# check for leaf recursively
if root.left:
printLeafNodes(root.left)
# If right child exists,
# check for leaf recursively
if root.right:
printLeafNodes(root.right)
# Driver Code
if __name__ == "__main__":
# Creates binary tree shown in
# above diagram
root = 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 tree
printLeafNodes(root)
node.py:
# Binary tree node
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
Эта программа берет корневой узел и печатает все конечные узлы слева направо. Наш базовый случай: либо 1) нет оставшихся узлов, либо 2) нет оставшихся листовых узлов.
Программа каждый раз следует соединениям каждого дочернего элемента, идущего влево, пока не найдет конечный узел. Программа печатает это значение, а затем повторяет эту подзадачу по другому пути узлов.
В конце концов, функция вернется, и все конечные узлы будут напечатаны слева направо.
Что изучать дальше
Рекурсия — неотъемлемая часть набора навыков любого разработчика Python. Рекурсивные вопросы часто занимают большую часть вопросов на собеседованиях по кодированию и необходимы для вопросов динамического программирования. Лучший способ изучить эти понятия — это получить практический опыт, отвечая на реальные вопросы на собеседовании.
Вот несколько вопросов, на которые следует ответить, если вы хотите продолжать совершенствоваться:
- 0–1 задача о рюкзаке
- Вопрос о сбалансированных скобках
- Преобразование дерева в двусвязный список
- Перевернуть стек
- Самый низкий общий предок
Вы можете найти пошаговые руководства по этим и другим вопросам рекурсивного интервью в Ace the Python Coding Interview Path от Educative. Этот Путь включает в себя всестороннюю практику и примеры вопросов для наиболее проверенных понятий, таких как рекурсия, динамическое программирование, параллелизм и ООП.
К концу вы сможете уверенно идти на следующее собеседование, зная, что вы отработали десятки наиболее часто задаваемых вопросов на собеседовании.
Продолжить чтение о Python и рекурсии на Educative
- 50 вопросов и ответов из интервью по Python
- Мастер-алгоритмы на Python для интервью по кодированию
- Рекурсия: Краткое руководство для программистов
Начать обсуждение
О каком еще ценном навыке Python вы хотели бы прочитать учебник? Была ли эта статья полезна? Дайте нам знать в комментариях ниже!
