我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
当前回答
我会用一个例子来解释。
你知道n!意味着什么?如果不是:http://en.wikipedia.org/wiki/Factorial
3! Is 1 times 2 times 3, which is 6
下面是一些伪代码
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
让我们试试吧:
factorial(3)
n是0吗?
no!
所以我们在递归中深入挖掘:
3 * factorial(3-1)
3 minus 1 is 2
2 == 0?
no!
所以我们要深入! 3 * 2 *阶乘(2-1) 2-1 = 1
1 == 0吗?
no!
所以我们要深入! 3 * 2 * 1 *阶乘(1-1) 1-1 = 0
0 == 0?
yes!
我们有一个小问题
所以我们有 3 * 2 * 1 * 1 = 6
我希望这对你有所帮助
其他回答
要理解递归,你只需要看看洗发水瓶上的标签:
function repeat()
{
rinse();
lather();
repeat();
}
这样做的问题是没有终止条件,递归将无限重复,或者直到洗发水或热水用完为止(外部终止条件,类似于吹你的堆栈)。
递归
方法A调用方法A调用方法A,最终这些方法A中的一个不会调用并退出,但这是递归,因为有东西调用了它自己。
递归的例子,我想打印出硬盘驱动器上的每个文件夹名称:(在c#中)
public void PrintFolderNames(DirectoryInfo directory)
{
Console.WriteLine(directory.Name);
DirectoryInfo[] children = directory.GetDirectories();
foreach(var child in children)
{
PrintFolderNames(child); // See we call ourself here...
}
}
你在用哪本书?
关于算法的标准教科书是Cormen & Rivest。我的经验是,它很好地教授了递归。
递归是编程中较难掌握的部分之一,虽然它确实需要本能,但它是可以学习的。但它确实需要一个好的描述,好的例子和好的插图。
此外,30页通常是很多的,30页是用一种编程语言编写的。在你从一本普通的书中理解递归之前,不要尝试用C或Java学习递归。
实际上,使用递归是为了降低手头问题的复杂性。你应用递归,直到你达到一个简单的基本情况,可以很容易地解决。这样就可以解决最后一个递归步骤。用这些递归步骤就可以解决最初的问题。
我会用一个例子来解释。
你知道n!意味着什么?如果不是:http://en.wikipedia.org/wiki/Factorial
3! Is 1 times 2 times 3, which is 6
下面是一些伪代码
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
让我们试试吧:
factorial(3)
n是0吗?
no!
所以我们在递归中深入挖掘:
3 * factorial(3-1)
3 minus 1 is 2
2 == 0?
no!
所以我们要深入! 3 * 2 *阶乘(2-1) 2-1 = 1
1 == 0吗?
no!
所以我们要深入! 3 * 2 * 1 *阶乘(1-1) 1-1 = 0
0 == 0?
yes!
我们有一个小问题
所以我们有 3 * 2 * 1 * 1 = 6
我希望这对你有所帮助