Понимание рекурсии на практических примерах

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

Рекурсия - увлекательная тема, которая может привести к созданию элегантных кодовых решений. Она также имеет пугающую репутацию: часто создает путаницу и считается необходимым препятствием для понимания многих популярных алгоритмов. Но не стоит волноваться! Рекурсию не так сложно понять, как научить ей.

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

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

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

Слово "рекурсия" происходит от латинского слова recurrere, означающего бежать или спешить назад, возвращаться, откатываться или повторяться.

Рекурсия в реальном мире

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

Люди часто сортируют стопки документов рекурсивным методом. Например, представьте, что вы сортируете 100 документов с названиями. Сначала вы раскладываете документы по стопкам по первой букве, а затем сортируете каждую стопку.

Циклы обратной связи в иерархической организации - это еще один пример рекурсии. Руководитель высшего звена просит руководителей высшего звена собрать отзывы от всех сотрудников компании. Каждый руководитель собирает своих непосредственных подчиненных и просит их собрать отзывы от своих непосредственных подчиненных. И так далее. Люди, не имеющие непосредственного подчинения, — конечные узлы дерева — оставляют свои отзывы. Отзывы отправляются вверх по дереву, и каждый менеджер добавляет свои собственные отзывы. В конечном итоге все отзывы возвращаются к высшему руководителю.

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

Примеры рекурсии в разработке программного обеспечения

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

Нужно ли мне использовать рекурсию?

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

С другой стороны, рекурсия подходит не для каждой ситуации. Вот еще несколько факторов, которые следует учитывать:

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

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

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

Пример 1

def count_down(count):
# нам нужен способ завершить наш обратный отсчет на 0 
# и предотвратить бесконечное продолжение рекурсии
    if count == 0:            
        print('Поехали!')                  
    else:                        
        print(count)             
        count_down(count-1)        
            
count_down(2)

1. вызывается функция count_down и значение count = 2
2. count_down вызывается рекурсивно, а count = 1
3. count_down вызывается рекурсивно, а count = 0

Базовый и рекурсивный варианты

Создание рекурсивной функции может быть выполнено в два этапа:

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

В рекурсивной функции эквивалент "счетной переменной" является аргументом рекурсивного вызова. Например, если мы ведем обратный отсчет до 0, нашим базовым вариантом будет вызов функции, которая получает 0 в качестве аргумента. Мы могли бы разработать рекурсивный шаг, который принимает переданный аргумент, уменьшает его на единицу и снова вызывает функцию с уменьшенным аргументом. Таким образом, мы бы перешли к 0 в качестве базового варианта.

Пример 2

names = [ "Li", [ "Tammy", [ "Will", "Bob" ], "Tomoko", "Jim" ],
    "Alex", [ "Colin", "Chad"], "Ann" ]

Предположим, вы хотите подсчитать количество конечных элементов в этом списке — объектов str самого низкого уровня - так, как если бы вы выровняли список. Конечными элементами являются "Li", "Tammy", "Will", "Bob", "Tomoko", "Jim", "Alex", "Colin", "Chad" и "Ann", поэтому ответ должен быть равен 10.

Простой вызов функции len() в списке не дает правильного ответа. функция len() подсчитывает объекты на верхнем уровне имен, которые представляют собой три конечных элемента "Li:", "Alex" и "Ann" и два подсписка ["Tammy", ["Will", "Bob"], "Tomoko", "Jim"] и ["Colin", "Chad"]:

for index, item in enumerate(names):
    print(index, item)

Вывод:

0 Li
1 ['Tammy', ['Will', 'Bob'], 'Tomoko', 'Jim']
2 Alex
3 ['Colin', 'Chad']
4 Ann

Что вам нужно, так это функция, которая просматривает всю структуру списка, включая подсписки. Алгоритм выглядит примерно так:

1. Пройдитесь по списку, изучая каждый пункт по очереди
2. Если вы найдете конечный элемент, то добавьте его к накопленному количеству
3. Если вы столкнулись с подсписком, выполните следующие действия:

• Перейдите в этот подсписок и аналогично пройдитесь по нему.
• Как только вы исчерпаете подсписок, вернитесь назад, добавьте элементы из подсписка в накопленное количество и возобновите просмотр родительского списка с того места, где вы остановились.

Рекурсивный проход по вложенному списку

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

В случае списка имен, если элемент является экземпляром типа list, то это подсписок. В противном случае это конечный элемент:

names = [ "Li", [ "Tammy", [ "Will", "Bob" ], "Tomoko", "Jim" ],
    "Alex", [ "Colin", "Chad"], "Ann" ]

print(isinstance(names[0], list)) #False
print(isinstance(names[1], list)) #True
print(isinstance(names[1][0], list)) #False
print(isinstance(names[1][1], list)) #True

Мы можем решить эту проблему, используя такой алгоритм, как этот:

def count_leaf_items(item_list):
    count = 0
    for item in item_list:
        if isinstance(item, list):
            count += count_leaf_items(item)
        else:
            count += 1
    return count

count_leaf_items(names) # выводит 10

Основные выводы

• Рекурсия - это концепция компьютерного программирования, с помощью которой вы можете разбить сложную задачу на более мелкие и простые версии, пока не найдете решение. Этот метод часто используется при работе со структурами данных и алгоритмами.
• Существуют три правила рекурсии: (1) у рекурсивного алгоритма должен быть базовый вариант, (2) он должен изменять свое состояние и переходить к базовому варианту, и (3) он должен вызывать сам себя рекурсивно.
• Любой алгоритм, который вы можете написать рекурсивно, вы также можете писать итеративно. Главное преимущество рекурсии в том, насколько она элегантна - она занимает меньше строк кода.
• Недостатком рекурсивных алгоритмов является то, что они часто занимают больше памяти, поскольку им приходится хранить данные во внутреннем стеке Python. Кроме того, их чтение и отладка могут быть сложнее, чем у итеративных алгоритмов, поскольку в рекурсивном алгоритме сложнее следить за тем, что происходит.
• Будьте осторожны с рекурсией, так как можно довольно легко перейти к написанию функции, которая никогда не завершается, или функции, которая использует избыточный объем памяти. Однако при правильном написании рекурсия может быть очень эффективным и математически элегантным подходом к программированию.

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