Member 10540766 Ответов: 3

Попытка лучше понять рекурсию

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

Может ли кто-нибудь объяснить, как вызывается рекурсия и как перемещаются части?
Это код:

private void btnExecute_Click(object sender, EventArgs e)
       {
           Hanoi(1, 2, 3, 3);
       }
       void Hanoi(int Tower1, int Tower2, int Tower3, int n)
       {
           if (n == 1)
               txtOutput.Text += "Move from " + Tower1 + " to " + Tower3 + "\r\n";
           if (n > 1)
           {
               Hanoi(Tower1, Tower3, Tower2, n - 1);
               Hanoi(Tower1, Tower2, Tower3, 1);
               Hanoi(Tower2, Tower1, Tower3, n - 1);
           }
       }


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

Move from 1 to 3
Move from 1 to 2
Move from 3 to 2
Move from 1 to 3
Move from 2 to 1
Move from 2 to 3
Move from 1 to 3

Sampath Lokuge

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

Sergey Alexandrovich Kryukov

Вы понимаете, как работает стек вызовов? Если вы это понимаете, это дает вам ключ к глубокому пониманию ключевых вещей: рекурсии, структурной обработки исключений и потоковой обработки...
—СА

phil2846

Я тоже рассматривал эту проблему в школе. Это мой вывод из окна txt, регистрирующего значения переменных по пути. a-это ссылка на то, какой метод был вызван. Что я в основном не понимаю на данный момент, так это то, как N увеличивается на одном из шагов. Я тоже не совсем понимаю логику рекурсивных вызовов.

вызов n=3 t1=1 t2=2 t3=3 a=1
вызов n=2 t1=1 t2=3 t3=2 a=1
вызов n=1 t1=1 t2=2 t3=3 a=1
Переход от 1 к 3
вызов n=1 t1=1 t2=3 t3=2 a=2
Переход от 1 к 2
вызов n=1 t1=3 t2=1 t3=2 a=3
Переход от 3 к 2
вызов n=1 t1=1 t2=2 t3=3 a=2
Переход от 1 к 3
вызов n=2 t1=2 t2=1 t3=3 a=3
вызов n=1 t1=2 t2=3 t3=1 a=1
Переход от 2 к 1
вызов n=1 t1=2 t2=1 t3=3 a=2
Переход от 2 к 3
вызов n=1 t1=1 t2=2 t3=3 a=3
Переход от 1 к 3

3 Ответов

Рейтинг:
26

CoderPanda

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

(Предполагая, что вы знаете, что такое Ханойская башня[^] головоломка есть...)

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

В вашем примере метод Ханой вызывает себя определенное количество раз и в конечном итоге
решение само собой[^] вот почему это рекурсивная процедура или метод.

В вашем коде башни - это стержни, а n(=3) - количество дисков. Вот логика, которой следует ваш код каждый раз, когда вызывается метод Ханоя:
Для перемещения N дисков с башни 1 Башня 3
переместите N-1 дисков из башни 1 в башню 2. Это оставляет диск n в одиночестве на башне 1.
перемещение дисков N 1 от башни к башне 3
переместите N-1 дисков из башни 2 в башню 3 так, чтобы они сидели на диске n

Теперь идите вперед и поставьте точку останова в Ханое() и продолжайте делать F10, пока не поймете это. Поставьте часы на Tower1, Tower2, Tower3 и n, которые вам помогут.

Если застрял, напиши ответ. Счастливого Кодирования.

Кроме того, если вы любитель программирования головоломок, как я, пожалуйста, смотрите этот[^]

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

Member 10540766

Итак, для каждого числа в Ханое(1,2,3,3) мы запускаем 3 подветви?

Например; для Ханоя (1) его:
Ханой(Tower1, Tower3, Tower2, n - 1);
Ханой(Tower1, Tower2, Tower3, 1);
Ханой(Tower2, Tower1, Tower3, n - 1);

Первая строка будет n(3) -1, что равно 2, но я не понимаю, что я делаю с подветвлениями.
Первая строка = ?
Вторая строка = ?
Третья строка = ?

Тогда для Ханоя(2) и (3) я все еще не понимаю этого, но, поняв, что происходит в первом вызове, я пойму все остальное.
Не могли бы вы объяснить это?

Рейтинг:
1

Mattias Högström

Да. Рекурсия может значительно упростить решение.
Но читать его может быть проблематично.

Вы пытаетесь понять 2 проблемы одновременно.

1. Как работает рекурсия.

Самая простая форма рекурсии-это вызов одной и той же функции из одного места кода.
Как вычисление факториала.

int CalcFactorial(int n)
{
если (n <= 1)
возврат 1;
ещё
return n * CalcFactorial(n-1)
}

За этим довольно легко следовать, потому что сложность невелика.
Есть только 1 ветвь, чтобы следовать. Он может быть легко преобразован в цикл for.

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

2. Как решить ханойские башни

Есть только 1 способ переместить кольцо.
положите меньшее поверх большего или на пустое место.

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

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

Я могу признаться, что мне тоже трудно следить за рекурсией. :Д
Для каждого вызова Hanoi () вы получаете 3 новых ответвления.
Я брал ручку и карандаш и писал дерево рекурсии.
Это лучший способ понять его.
Я бы определенно сделал это в этом случае, так как количество звонков очень мало.

Member 10540766

Итак, для каждого числа в Ханое(1,2,3,3) мы запускаем 3 подветви?

Например; для Ханоя (1) его:
Ханой(Tower1, Tower3, Tower2, n - 1);
Ханой(Tower1, Tower2, Tower3, 1);
Ханой(Tower2, Tower1, Tower3, n - 1);

Первая строка будет n(3) -1, что равно 2, но я не понимаю, что я делаю с подветвлениями.
Первая строка = ?
Вторая строка = ?
Третья строка = ?

Тогда для Ханоя(2) и (3) я все еще не понимаю этого, но, поняв, что происходит в первом вызове, я пойму все остальное.
Не могли бы вы объяснить это?

Mattias Högström

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

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

Программа сначала полностью завершает все левые ветви.
С самого начала все кольца находятся на первой башне.
Входим в Ханой(1,2,3,3)
Затем мы входим в рекурсивный Ханой(1,3,2, 3-1)
Затем мы снова вводим рекурсивную версию Ханоя(1,2,3 2-1).
Затем он печатает "перейти от башни №1 к башне №3", потому что n == 1
#1 и #3-это башня 1 и башня 3, в первый раз.
Это происходит на глубине 2.
Затем он возвращается на глубину 1,и там он должен продолжить среднюю и правую ветвь.

То, что он делает, это делает сложное движение, которое требует трех подходов.
При втором звонке он принимает во внимание, что кольца сдвинулись при первом звонке.
(Обходит вокруг башни). Затем он продолжает двигать кольца.

Рекурсия обычно не так сложна.
Такое решение не является чем-то, что вы просто придумали случайно.
Обычно вы делаете решение или его часть (дерево с ходами) на бумаге.
Затем обобщите и абстрагируйте алгоритм.

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

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

Member 10540766

У меня возникли проблемы с выполнением кода даже с точкой останова, есть какие-нибудь советы по более простому способу его выполнения? Или выписывать его шаг за шагом??

Рейтинг:
1

Prasad Avunoori 

Hi,

If you would have known calling a method in Object oriented programming understanding Recursion is not a big problem

1. Calling a method itself by changing the parameters(Hanoi(Tower1, Tower3, Tower2, n - 1);
) until it satisfies a condition(if (n == 1))

Member 10540766

Я понимаю, что он зовет себя снова и снова, пока не будут выполнены условия, но я пытаюсь понять, если:

Ханой(1, 2, 3, 3);

означает, что n = 1, затем 2, затем 3, затем 3.
Или если его
Ханой(международный Tower1, инт Tower2, Tower3 инт, инт Н)
Ханой(1, 2, 3, 3);

Это означает, что tower1 = 1, tower2 = 2, tower3 = 3, n = 3 ?