Ознакомьтесь с моим визуальным пособием по рекурсии (поскольку изображение стоит 1000 слов)

1656669857 oznakomtes s moim vizualnym posobiem po rekursii poskolku izobrazhenie stoit

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

Немного деталей:

  • Код написан на языке Python
  • Синие прямоугольники представляют текущую область действия функции
  • Соединительные линии – это возвращающая функция.

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

Мы рассмотрим три проблемы: поиск анаграмм строки, сортировка слиянием и Ханойская башня. Постепенно они становятся несколько более нюансированными, так что осторожно!

Ниже я расскажу больше о рекурсии.

Анаграммы

def anagrams(s):
    if s == "":
        return [s]
    else :
        ans = []
    for w in anagrams(s[1: ]):
        for pos in range(len(w) + 1):
            ans.append(w[: pos] + s[0] + w[pos: ])
    return ans

anagrams("abc")

# returns ['abc', 'bac', 'bca', 'acb', 'cab', 'cba']
1*Z67ClqdjbnaZvkASvFOxNg
1*YLyylfd6hKYJ9rhW4JrBHQ
анаграммурсия

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

Также обратите внимание, как переменная ans все значения добавляются при исходном вызове функции (1).

Сортировка слиянием

def merge(lst1, lst2, lst3):
    i1, i2, i3 = 0, 0, 0
    n1, n2 = len(lst1), len(lst2)
    while i1 < n1 and i2 < n2:
        if lst1[i1] < lst2[i2]:
            lst3[i3] = lst1[i1]
            i1 = i1 + 1
        else:
            lst3[i3] = lst2[i2]
            i2 = i2 + 1
        i3 = i3 + 1
    
    # unequal length of lists? Check both
    while i1 < n1: 
        lst3[i3] = lst1[i1]
        i1 = i1 + 1
        i3 = i3 + 1
    
    while i2 < n2:
        lst3[i3] = lst2[i2]
        i2 = i2 + 1
        i3 = i3 + 1

def mergeSort(nums):
    n = len(nums)
    if n > 1:
        m = n // 2
        nums1, nums2 = nums[:m], nums[m:]
        mergeSort(nums1)
        mergeSort(nums2)
        merge(nums1, nums2,nums)
    
numbers = [7, 4, 6, 2, 8]
mergeSort(numbers)

print(numbers)
# returns sorted numbers (function altered underlying data structure)
1*t9czQmsarojfOozmxL8yJw
1*nnvoyLfp3vkppsXPG0MOdg
recursamerged

Опять же обратите внимание на порядок, в котором выполняется каждый вызов. Чтобы понять, как работает слияние, посмотрите на него внимательно. По сути, у вас есть три указателя и две отсортированные половины первоначального списка, которые постоянно сравниваются. Наименьшее число при этом сравнении устанавливается по индексу, на который указывается в исходном списке (начиная с индекса 0).

Несколько примечаний, если вы не привыкли к Python. Если функция ничего не возвращает, она возвращает значение None . Вы можете увидеть часто возвращаемое значение None на моих диаграммах, поскольку у них нет явных операторов возврата mergeSort.

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

Ханойская башня

Вот краткая история как примечание — я нашел это довольно поэтическим поступлением в Ханойскую башню:

«Где-то в отдаленном регионе мира есть монастырь очень набожного религиозного ордена. Монахам поручено священное задание, сохраняющее время для Вселенной. В начале всего монахам дали стол, поддерживающий три вертикальных стойки. На одном из столбов была куча из 64 концентрических золотых дисков. Диски имеют разный радиус и складываются в форме красивой пирамиды. Монахам поручено перенести диски с первого столба на третий. Когда монахи выполнят свою задачу, все рассыплется на прах и вселенная закончится». — Джон Зелл, Программирование на Python: Введение в информатику (2004)

def moveTower(n, source, dest, temp):
    if n == 1:
        print("Move disk from", source, "to", dest+".")
    else:
        moveTower(n-1, source, temp, dest)
        moveTower(1, source, dest, temp)
        moveTower(n-1, temp, dest, source)
    
 def hanoi(n):
    moveTower(n, "A", "C", "B")
1*X-VwEe3eLmdZ0e2fKLiZMQ
1*KwKjFU1KLTZun28Kvni0CQ
1*dbkrNWmhXfpwJv2eJHINhA
1*IBrJOSrMZqF6Z0O5VDwPsQ
1*M19VyJnzn0mPfE4-CuFAcg
1*AKUhFf1l7tcgF88Pp5MaFA
1*7-1o9KOOaEKBScXEQskabA
hanoision

Перемещение блоков основано на математическом принципе.

Из статьи в Википедии:

  1. двигаться м − 1 диск со ст. источник к темп колышек Это оставляет диск м как верхний диск на исходном колышке.
  2. Переместите диск м от источник к дест колышек
  3. Переместите м − 1 диски, которые мы только что поместили на запасной с темп к дест колышек, поэтому они размещаются поверх диска м не нарушая правил.

Но как понять этот принцип? Ну, проверь это.

1*XVjr4Ue0FtF2BUj1W2E-Tw
точность

Обратите внимание: три правила повторяются (черный текст), за исключением случаев, когда выполняется правило 2 (синий текст), поскольку алгоритм не достигает базового случая.

1*Rt-CKWzyXM1VP-mwD8XuuA
в основном

Несколько слов о рекурсии

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

Основная концепция рекурсии такова:

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

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

Если вы хотите развиваться в сфере рекурсивного решения задач, то вам следует изучать математику. Они одно и то же. Но рассмотрение математики выходит за рамки данной статьи. Эта статья в Википедии является хорошей подготовкой для начала.

Вот и все. Я должен поблагодарить, абсолютно и полностью, «Структуры данных и алгоритмы с использованием Python и C++» Дэвида М. Рида, а также Джона Зелла, поскольку именно оттуда была взята эта замечательная цитата и алгоритмы.

И вот хороший вид на пространство, потому что рекурсия немного похожа на это.

1*PPXnzjpCdxuMiz9OJdhe8w

Добавить комментарий

Ваш адрес email не будет опубликован.