试图更好地理解递归 [英] Trying to understand recursion better

问题描述

您好。

我正在研究递归，并试图理解它。

我正在研究一个例子，需要一步一步地弄清楚发生了什么。

到目前为止，我理解它的某些部分，但似乎无法弄清楚它是如何组合在一起的。



任何人都可以解释如何正在调用递归以及如何移动部件？

这是代码：

 < span class =code-keyword> private   void  btnExecute_Click（ object  sender，EventArgs e ）
 {
 Hanoi（ 1 ， 2 ， 3 ， 3 ）; 
} 
  void 河内（ int  Tower1， int  Tower2， int  Tower3， int  n）
 {
  if （n ==  1 ）
 txtOutput.Text + =  从 + Tower1 +   to + Tower3 +   \\\\ n; 
  if （n >   1 ）
 {
 Hanoi（Tower1，Tower3，Tower2，n  -   1 ）; 
 Hanoi（Tower1，Tower2，Tower3， 1 ）; 
 Hanoi（Tower2，Tower1，Tower3，n  -   1 ）; 
} 
} 

正在输出以下内容，我需要弄清楚它是如何工作的：

从1移动到3 
从1移动到2 
从3移动到2 
从1移动至3 
从2移至1 
从2移至3 
从1移至3 

解决方案

首先，感谢您提出一个智力问题。不要经常看到这些，我个人非常喜欢谈论这些。我希望你自己理解，我相信你可以。我只会解释一下代码来帮助你。



（假设你知道什么是河内塔 [ ^ ]难题是...）



简而言之 - 递归意味着调用自己。或者重复应用相同的程序。



在你的例子中，河内方法调用自己一定次数并最终

自行解决 [ ^ ]这就是为什么它是递归程序或方法。



在你的代码，塔是杆，n（= 3）是光盘的数量。以下是每次调用Hanoi方法时您的代码遵循的逻辑：

将n个光盘从1号塔移动到3号楼

将n-1个光盘从1号塔移到塔2.这在第1塔上留下了光盘。

将光盘n从1号塔移动到3号楼

将n-1碟从2号塔移到3号塔，这样它们就可以了坐在光盘上



现在继续在河内（）中断一个断点并继续做F10直到你理解它为止。将手表放在Tower1，Tower2，Tower3和n上，这将对您有所帮助。



如果卡住，请回信。快乐的编码。



此外，如果您喜欢像我这样的编程拼图，请参阅此 [ ^ ]



[请接受/投票给你的答案或解决方案，以鼓励他人]

是的。递归可以简化一个解决方案。

但是阅读它可能会有问题。



你试图同时理解2个问题时间。



1.递归如何工作。



最简单的递归形式是相同的从代码中的一个地方起作用。

喜欢计算阶乘。



int CalcFactorial（int n）

{

if（n< = 1）

返回1;

其他

返回n * CalcFactorial（n - 1）

}



这个很容易理解，因为复杂性很低。

只有一个分支可供使用。它可以很容易地转换为for循环。



上面的例子非常复杂，

因为递归的深度是很难掌握。

所有这些结果都会影响结果。



2.如何解决河内的塔楼/>


移动戒指的方法只有一种。

在较大或空旷的地方放一个小的。



为了移动3个相互重叠的戒指。

你把最小的戒指放在一根棍子上。

将中间放在另一个自由杆上。

将较小的中间移动到中间。

移动最大的一个。

移动最小的一个。

将中间移动到最大的一个。最后移动最小的在中间的一个。

完成。



对函数的三次调用对应于可用塔的数量，

和间接如何移动它们之间的环。



我可以承认我也很难跟进递归。 ：D

每次拨打Hanoi（），你都会得到3个新的子分支。

我会用笔和笔写出递归树。

这是了解它的最好方法。

我肯定会在这种情况下这样做，因为调用次数很少。

 
 如果你就知道调用方法 in 面向对象编程理解递归  不一个大问题
 
  1 。通过更改参数调用方法本身（Hanoi（Tower1，Tower3，Tower2，n  -   1 ）; 
）直到满足条件（ if （n ==  1 ））

Hi.
I am studying recursion at the moment and trying to understand it well.
Got an example im working on and need to figure out step by step what is happening.
So far i understand certain parts of it, but can't seem to figure out how it all goes together.

Can anyone please explain how the recursion is being called and how parts are being moved?
This is the code:

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);
           }
       }

It is outputting the following and i need to figure out how its working:

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

解决方案

First of all, thanks for asking an intellectual question. Don't get to see these often and I, personally, absolutely love to talk about these. I would like you to understand it yourself and I am sure you can. I will only explain the code a bit more to help you out.

(Assuming you know what a Tower of Hanoi[^] puzzle is...)

In short - Recursion means invoking itself. Or the repeated application of the same procedure on itself.

In your example, the method Hanoi is invoking itself for certain number of times and eventually
solving itself[^] which is why it is a recursive procedure or method.

In your code, Towers are the rods and n(=3) is the number of discs. Here is the logic your code follows every time the Hanoi method is called:
To move n discs from Tower 1 to Tower 3
move n−1 discs from Tower 1 to Tower 2. This leaves disc n alone on Tower 1.
move disc n from Tower 1 to Tower 3
move n−1 discs from Tower 2 to Tower 3 so they sit on disc n

Now go ahead and put a break point in Hanoi() and keep doing F10 until you understand it. Put watches on Tower1, Tower2, Tower3 and n which will help you.

If stuck, write back. Happy Coding.

Also, if you are a lover of programming puzzles like me, please see this[^]

[Please accept/up-vote answers or solutions that work for you to encourage others]

Yes. Recursion can simplify a solution quite a lot.
But reading it may be problematic.

You are trying to understand 2 problems at the same time.

1. How the recursion works.

The easiest form of recursion is calling the same function from just one place in the code.
Like calculating the factorial.

int CalcFactorial(int n)
{
if (n <= 1)
return 1;
else
return n * CalcFactorial(n - 1)
}

This one is quite easy to follow, because the complexity is low.
There is only 1 branch to follow. It can easily be converted to a for loop.

Your example above is quite complex to follow,
because the depth of the recursion is hard to grasp.
And the result from all of them influences the result.

2. How to solve the towers of Hanoi

There is only 1 way to move a ring.
put a smaller on top of a bigger or on an empty place.

In order to move 3 rings which are on top of each other.
You put the smallest on one stick.
Put the middle on the other free stick.
Move the smaller to the middle one.
Move the biggest one.
Move the smallest away from the middle one.
move the middle one to the biggest, and finally move the smallest on top of the middle one.
Done.

The three calls to the function corresponds to the number of towers available,
and indirectly how you move the rings between them.

I can confess that I have hard time to follow the recursion too. :D
For each call to Hanoi(), you get 3 new sub branches.
I would take a pen and pencil and write out the recursion tree.
That is the best way to understand it.
I would definitely do it in this case, since the number of calls are so few.

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))

这篇关于试图更好地理解递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！