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

Ответ 1

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

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

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

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

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

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

• Математические операции: Экспоненциальность и каждая математическая операция, о которой вы можете думать.
• Обработка строк: Palindrome - очень хорошее упражнение. Также полезно найти слова в сетке.
• Узнайте о структурах древовидных данных: Это, в частности, ИМО - лучшая подготовка. Деревья - это рекурсивные структуры данных. Узнайте об их обходах (порядок, порядок, предзаказ, расчет его высоты, его диаметра и т.д.). Практически каждая операция по древовидной структуре данных - отличное упражнение.
• Комбинаторные проблемы: Очень важно, комбинации, перестановки и т.д.
• Поиск пути: алгоритм Ли, алгоритмы лабиринтов и т.д.

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

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

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

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

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

Чтобы справиться с рекурсией, вам нужна первая главная рекурсия:)

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

Ответ 2

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

Для полноты здесь приведен один и тот же алгоритм в Lisp:

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

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

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

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

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

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

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

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

... или...

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

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

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

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

...

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

...

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

Также Башня Ханоя. Решение легко, если вы заявите следующее:

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

Ответ 4: Да, если разбить массив с помощью шарнира, можно сортировать весь массив путем сортировки двух частей. Это быстрый вид.

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

Ответ 5

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

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

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

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

Ответ 6

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

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

   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)

Круто! И ждать, move3 и move2 сейчас очень похожи, и это имеет смысл. Для любой размерной задачи мы можем переместить все, кроме одного из дисков, на привязку 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')

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