我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
当前回答
如果你想要一本很好地用简单的术语解释递归的书,可以看看Gödel,埃舍尔·巴赫:道格拉斯·霍夫施塔特的《永恒的金辫子》,特别是第五章。除了递归,它还能很好地以一种可理解的方式解释计算机科学和数学中的许多复杂概念,一个解释建立在另一个解释的基础上。如果你以前没有接触过这类概念,这可能是一本非常令人兴奋的书。
其他回答
http://javabat.com是一个有趣而令人兴奋的练习递归的地方。他们的例子开始时相当简单,然后逐步扩展(如果你想这么做的话)。注意:他们的方法是在实践中学习。这是我写的一个递归函数,用来替换for循环。
for循环:
public printBar(length)
{
String holder = "";
for (int index = 0; i < length; i++)
{
holder += "*"
}
return holder;
}
这是做同样事情的递归。(请注意,我们重载了第一个方法,以确保它像上面那样使用)。我们还有另一种方法来维护索引(类似于上面的for语句)。递归函数必须维护自己的索引。
public String printBar(int Length) // Method, to call the recursive function
{
printBar(length, 0);
}
public String printBar(int length, int index) //Overloaded recursive method
{
// To get a better idea of how this works without a for loop
// you can also replace this if/else with the for loop and
// operationally, it should do the same thing.
if (index >= length)
return "";
else
return "*" + printBar(length, index + 1); // Make recursive call
}
简而言之,递归是一种编写更少代码的好方法。在后面的printBar中,请注意我们有一个if语句。如果我们的条件已经达到,我们将退出递归并返回到前一个方法,该方法返回到前一个方法,等等。如果我发送一个printBar(8),我得到********。我希望通过一个简单函数的例子,它做的事情与for循环相同,这可能会有所帮助。不过,您可以在Java Bat中进行更多的练习。
你在用哪本书?
关于算法的标准教科书是Cormen & Rivest。我的经验是,它很好地教授了递归。
递归是编程中较难掌握的部分之一,虽然它确实需要本能,但它是可以学习的。但它确实需要一个好的描述,好的例子和好的插图。
此外,30页通常是很多的,30页是用一种编程语言编写的。在你从一本普通的书中理解递归之前,不要尝试用C或Java学习递归。
你的大脑爆炸是因为它进入了无限递归。这是初学者常犯的错误。
信不信由你,你已经理解了递归,你只是被一个常见的,但错误的函数比喻拖了下来:一个小盒子,里面有东西进进出出。
而不是考虑一个任务或过程,比如“在网上找到更多关于递归的知识”。这是递归的,没有问题。要完成这个任务,你可以:
a) Read a Google's result page for "recursion" b) Once you've read it, follow the first link on it and... a.1)Read that new page about recursion b.1)Once you've read it, follow the first link on it and... a.2)Read that new page about recursion b.2)Once you've read it, follow the first link on it and...
如您所见,您已经做了很长一段时间的递归工作,没有出现任何问题。
你会坚持做这个任务多久?永远,直到你的大脑爆炸?当然不是,只要你相信你已经完成了任务,你就会停在一个给定的点上。
当要求你“在网上找到更多关于递归的知识”时,没有必要指定这一点,因为你是一个人,你可以自己推断。
计算机无法推断任何东西,所以你必须包含一个明确的结尾:“在网上找到更多关于递归的知识,直到你理解它或你阅读了最多10页”。
您还推断应该从谷歌的结果页面开始进行“递归”,这也是计算机无法做到的。递归任务的完整描述还必须包括一个显式的起点:
“在网上找到更多关于递归的知识,直到你理解它,或者你已经阅读了最多10页,并从www.google.com/search?q=recursion开始”
要想全面了解,我建议你试试下面这些书:
普通Lisp:符号计算的简单介绍。这是对递归最可爱的非数学解释。 小阴谋家。
这与其说是一个问题,不如说是一个抱怨。关于递归你有更具体的问题吗?就像乘法一样,人们不会写很多关于它的东西。
说到乘法,想想这个。
问题:
* b是什么?
答:
如果b = 1,就是a。 否则就是a+a*(b-1)
* (b - 1)是什么?请参考上面的问题来解决这个问题。
要理解递归,你只需要看看洗发水瓶上的标签:
function repeat()
{
rinse();
lather();
repeat();
}
这样做的问题是没有终止条件,递归将无限重复,或者直到洗发水或热水用完为止(外部终止条件,类似于吹你的堆栈)。