Рекурсия в Python

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

Сегодня мы поможем вам освежить свои навыки рекурсивного программирования на Python и рассмотрим 6 практических задач, чтобы получить практический опыт.

Что такое рекурсия?

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

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

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

Это приводит к поведению, аналогичному циклам 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)>

Рекурсивные решения лучше всего подходят, когда проблема имеет чёткие подзадачи, которые необходимо повторить, и если вы не уверены, сколько раз вам нужно будет выполнить цикл с итеративным решением.

Например, если вы хотите создать программу-функцию факториала, которая находит факториал неизвестного числа.

def factorial(n):

    if n==0:

        return 1

    return n*factorial(n-1)

num = 5

print(factorial(num))

Прямая против косвенной рекурсии

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

Например, functionAзвонки functionB, которые потом звонят function Aснова.

• Прямой

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 вложенных шагов. Хотя это может показаться большим, это становится проблемой при работе с большими структурами, такими как списки и массивы. Это можно изменить по вашему усмотрению с помощью 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)

Мы хотим напечатать каждое число дважды, за исключением того, 0что оно печатается только один раз в середине. Это позволяет нам узнать, что if (targetNumber <= 0)это наш базовый вариант.

Таким образом, наш рекурсивный случай — это строки 7–9.

В строке 8 вы можете увидеть рекурсивный вызов printPattern(targetNumber — 5), который переводит нашу программу на следующий рекурсивный шаг.

Строка 9 печатает финал 10и запускается только один раз, как и после рекурсивного вызова.

Помните, что в рекурсивном цикле повторяется только поведение до рекурсивного вызова.

Взгляните на эту блок-схему программы, чтобы увидеть, как связаны шаги программы:

Давайте посмотрим на стек вызовов по мере выполнения этой программы:

Теперь, когда мы разобрали эту рекурсивную программу, давайте рассмотрим некоторые применения рекурсии.

Рекурсия Python с числами

Последовательность Фибоначчи

Сначала мы рассмотрим классический пример рекурсии: последовательность Фибоначчи. Эта программа берёт заданное число и возвращает его числа Фибоначчи.

Каждый раз, когда цикл повторяется, 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))

Наша программа начинается с заданного числа и на каждом рекурсивном шаге добавляет цифру на единицу ниже, пока не достигнет 1.

Базовый вариант находится в строке 3 if targetNumber ==1,. В рекурсивном случае текущее значение targetNumberthen вызовов 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»))

Удаление вкладок из пустой строки «просто вернёт пустую строку». Следовательно, наш базовый случай будет, когда наша исходная строка пуста (строка 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))

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

Базовые случаи этой проблемы — это когда в массиве содержится 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

• connectedList.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

В приведённом выше фрагменте кода мы передаём наш связанный список 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) нет оставшихся листовых узлов.

Программа отслеживает соединения каждого дочернего элемента каждый раз, уходя влево, пока не найдёт листовой узел. Программа печатает это значение, а затем повторяет эту подзадачу для другого пути узлов.

В конце концов, функция вернётся, и все листовые узлы будут напечатаны слева направо.