Освоение рекурсивного программирования

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

Лучший способ освоить:

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

Кроме того, всегда полезно выяснить, как небольшой экземпляр проблемы поможет вам найти решение более крупного экземпляра проблемы. Например, как вы можете построить решение для входа n, имея уже решение для входа n-1.

Рекурсивно рекурсивно решайте любую проблему, о которой вы только можете подумать. Да, Hanoi Towers — не очень хороший пример, его рекурсивные решения — очень умное решение. Пробуйте более легкие задачи, почти элементарные задачи.

Список проблем

1. Математические операции: возведение в степень и все математические операции, которые только можно придумать.
2. Обработка строк. Палиндром — очень хорошее упражнение. Поиск слов в сетке также полезен.
3. Узнайте о древовидных структурах данных. Это, в частности, лучшее обучение по ИМО. Деревья — это рекурсивные структуры данных. Узнайте об их обходах (inorder, postorder, preorder, вычислите его высоту, диаметр и т. д.). Почти каждая операция над древовидной структурой данных — это отличное упражнение.
4. Комбинационные задачи. Очень важны комбинации, перестановки и т. д.
5. Поиск пути: алгоритм Ли, алгоритмы лабиринта и т. д.

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

Язык программирования

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

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

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

Чтобы освоить рекурсию, вам нужно сначала освоить рекурсию :)

Надеюсь это поможет!

Мой совет: доверьтесь, что рекурсивная функция "делает свою работу", т. е. выполняет свою спецификацию. Зная это, вы можете создать функцию, которая решает большую проблему, но при этом соответствует спецификации.

Как решить проблему с ханойскими башнями? Предположим, что существует функция Hanoi(N), способная перемещать стопку из N дисков, не нарушая правил. Используя эту функцию, вы легко реализуете Hanoi'(N+1): выполните Hanoi(N), переместите следующий диск и снова выполните Hanoi(N).

Если работает Hanoi(N), то работает и Hanoi'(N+1), не нарушая правил. Чтобы завершить аргумент, вы должны убедиться, что рекурсивные вызовы завершаются. В этом случае, если вы можете решить Ханой (1) не рекурсивно (что тривиально), вы закончили.

Используя этот подход, вам не нужно беспокоиться о том, как все будет происходить на самом деле, вам гарантировано, что это работает. (При условии, что вы переходите к все более и более мелким экземплярам проблемы.)

Другой пример: рекурсивный обход бинарного дерева. Предположим, что функция Visit(root) выполняет эту работу. Тогда if left -> Visit(left); if right -> Visit(right); print root выполнит эту работу! Потому что первый вызов напечатает левое поддерево (не беспокойтесь как), а второй - правое поддерево (не беспокойтесь как), и корень тоже будет напечатан.

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

Другой пример: быстрая сортировка. Предположим, у вас есть функция, которая сортирует массив на месте, пусть Quicksort. Вы будете использовать его следующим образом: перемещайте маленькие элементы перед большими элементами, на месте, сравнивая их с хорошо выбранным «основным» значением (на самом деле, любое значение из массива может подойти). Затем отсортируйте мелкие элементы с помощью функции Quicksort, а крупные таким же образом, и готово! Не нужно задаваться вопросом о точной последовательности разделов, которые будут иметь место. Завершение обеспечивается, если вы избегаете пустых подмассивов.

Последний пример, треугольник Паскаля. Вы знаете, что элемент представляет собой сумму двух над ним с единицами по бокам. Итак, с закрытыми глазами, C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1). Вот и все!

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

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

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

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

Изучение функционального языка, безусловно, поможет вам мыслить рекурсивно. Я бы порекомендовал либо Haskell, либо Lisp (или Clojure). Приятно то, что вам не нужно разбираться в «сложных моментах» любого из этих языков, прежде чем перейти к рекурсии. Чтобы узнать о рекурсии, вам не нужно достаточно знать ни один из этих языков, чтобы заниматься "настоящим" программированием.

Синтаксис сопоставления шаблонов в Haskell означает, что базовые случаи легко увидеть. В Haskell факториал выглядит так:

factorial 0 = 1
factorial n = n * factorial (n - 1)

... что точно эквивалентно процедурному языку:

int factorial(n) {
    if(n==0) {
         return 1;
    } else {
         return n * factorial(n-1)
    }
}

... но с меньшим количеством синтаксиса, чтобы скрыть концепцию.

Для полноты картины тот же алгоритм на Лиспе:

(defun factorial (n)
   (if (== n 0)
       1
       (* n (factorial (- n 1)))))

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

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

 addone [] = []
 addone (head:tail) = head + 1 : addone tail

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

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

В более общем смысле подумайте о таких проблемах:

«Могу ли я решить небольшую часть этой проблемы и оставить себе ту же проблему, только меньшую?».

... or ...

«Легко ли было бы решить эту проблему, если бы все остальное уже было решено?».

Так, например, factorial(n) легко решить, если вы знаете factorial(n-1), что предполагает рекурсивное решение.

Оказывается, таким образом можно думать о многих проблемах:

«Сортировка списка из 1000 элементов кажется сложной, но если я выберу случайное число, отсортирую все числа меньше этого, а затем отсортирую все числа больше этого, я готов». (В конце концов сводится к сортировке списков длины 1)

...

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

...

«Посетить каждый файл в этом дереве каталогов сложно, но я могу одинаково просматривать файлы в базовом каталоге и угрожать подкаталогам».

Как и Ханойская башня. Решение легко, если вы сформулируете его так:

 To move a stack from a to c:
  If the stack is of size 1
      just move it.
  otherwise
      Move the stack minus its largest ring, to b (n-1 problem)
      Move the largest ring to c (easy)
      Move the stack on b to c (n-1 problem)

Мы упростили задачу, набросав два явно сложных шага. Но эти шаги — это снова та же проблема, но «на один меньше».

Вам может оказаться полезным вручную выполнить рекурсивный алгоритм, используя листы бумаги для представления стека вызовов, как описано в этом ответе: Понимание раскручивания стека в рекурсии (обход дерева)

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

Рекурсия — это удобный способ реализации парадигмы «разделяй и властвуй»: когда вам нужно решить определенную проблему, действенный подход — разбить ее на задачи одинакового характера, но с меньшими затратами. размер. Повторяя этот процесс, вы в конечном итоге будете работать над проблемами настолько маленькими, что их можно будет легко решить другим методом.

Вопрос, который вы должны задать себе: «Могу ли я решить эту проблему, решая ее части?». При положительном ответе применяется известная схема:

• разбить проблему на подзадачи рекурсивно, пока размер не станет маленьким,

• решить подзадачи прямым методом,

• объединить решения в обратном порядке.

Обратите внимание, что разделение может быть сделано на две или более частей, и они могут быть сбалансированы или нет.

Например: могу ли я отсортировать массив чисел, выполнив частичную сортировку?

Ответ 1: да, если я оставлю последний элемент и отсортирую остальные, я смогу отсортировать весь массив, вставив последний элемент в нужное место. Это сортировка вставками.

Ответ 2: да, если я найду самый большой элемент и перенесу его в конец, я смогу отсортировать весь массив, отсортировав оставшиеся элементы. Это сортировка выбором.

Ответ 3: да, если я отсортирую две половины массива, я могу отсортировать весь массив, объединив две последовательности, используя вспомогательный массив для перемещений. Это сортировка слиянием.

Ответ 4: да, если я разбиваю массив с помощью сводки, я могу отсортировать весь массив, отсортировав две части. Это быстрая сортировка.

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

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

Я только что сам разобрался с проблемой Ханойских башен и изучил собственное мышление. Я начал с проблемы размера один:

   We have one disk on peg A.
   *** Move it to peg C.
   Done!

Теперь на двоих.

   We have two disks on peg A.
   I need to use peg B to get the first disk out of the way.
   *** Move from peg A to peg B
   Now I can do the rest
   *** Move from peg A to peg C
   *** Move from peg B to peg C
   Done!

Теперь на троих.

Все начинает становиться немного интереснее. Решение не столь очевидно. Однако я понял, как переместить два диска с одного стержня на другой, поэтому, если бы я мог переместить два диска с стержня A на стержень B, затем переместить один диск с стержня A на стержень C, а затем два диска с стержня B. чтобы привязать C, я был бы сделан! Моя логика для случая с двумя дисками сработает, разве что штифты разные. Если мы поместим логику в функцию и создадим параметры для привязок, то сможем повторно использовать логику.

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   print 'Move from peg '+from_peg+' to peg '+other_peg
   # Now I can do the rest
   print 'Move from peg '+from_peg+' to peg '+to_peg
   print 'Move from peg '+other_peg+' to peg '+to_peg

Тогда логика такая:

       move2('A','B','C')
       print 'Move from peg A to peg C'
       move2('B','C','A')

Я могу сделать это проще, используя функцию move1:

def move1(from_peg,to_peg):
    print 'Move from '+from_peg+' to '+to_peg

Теперь моя функция move2 может быть

def move2(from_peg,to_peg,other_peg):
   # We have two disks on from_peg
   # We need to use other_peg to get the first disk out of the way
   move1(from_peg,other_peg,to_peg)
   # Now I can do the rest
   move1(from_peg,to_peg)
   move1(other_peg,to_peg)

Хорошо, а четыре?

Похоже, я могу применить ту же логику. Мне нужно получить три диска от привязки A к привязке B, затем один от A к C, затем три от B к C. Я уже решил переместить три, но с неправильными привязками, поэтому я обобщу это:

def move3(from_peg,to_peg,other_peg):
   move2(from_peg,other_peg,to_peg)
   move1(from_peg,to_peg)
   move2(other_peg,to_peg,from_peg)

Прохладный! И подождите, ход 3 и ход 2 теперь очень похожи, и в этом есть смысл. Для задачи любого размера мы можем переместить все диски, кроме одного, на привязку B, затем переместить один диск из A в C, затем переместить все диски с привязки B на привязку C. Таким образом, наша функция перемещения может просто взять количество дисков как параметр:

def move(n,from_peg,to_peg,other_peg):
    move(n-1,from_peg,other_peg,to_peg)
    move1(from_peg,to_peg)
    move(n-1,other_peg,to_peg,from_peg)

Это выглядит очень похоже, но не работает в случае, когда n==1, потому что в итоге мы вызываем move(0,...). Итак, нам нужно справиться с этим:

def move(n,from_peg,to_peg,other_peg):
    if n==1:
        move1(from_peg,to_peg)
    else:
        move(n-1,from_peg,other_peg,to_peg)
        move1(from_peg,to_peg)
        move(n-1,other_peg,to_peg,from_peg)

Превосходно! Как насчет задачи размером пять? Мы просто вызываем move(5,'A','C','B'). Похоже, что любой размер задачи — это одно и то же, поэтому наша основная функция такова:

def towers(n):
    move(n,'A','C','B')

и мы закончили!