我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
当前回答
你在用哪本书?
关于算法的标准教科书是Cormen & Rivest。我的经验是,它很好地教授了递归。
递归是编程中较难掌握的部分之一,虽然它确实需要本能,但它是可以学习的。但它确实需要一个好的描述,好的例子和好的插图。
此外,30页通常是很多的,30页是用一种编程语言编写的。在你从一本普通的书中理解递归之前,不要尝试用C或Java学习递归。
其他回答
递归函数就像弹簧,每次调用都要压缩一点。在每一步中,您将一些信息(当前上下文)放在堆栈上。当到达最后一步时,释放弹簧,立即收集所有值(上下文)!
不确定这个比喻是否有效…: -)
无论如何,除了经典的例子(阶乘是最糟糕的例子,因为它效率低,很容易被平化,Fibonacci, Hanoi…),这些都有点人为(我很少,如果有的话,在实际编程案例中使用它们),看看它真正被使用的地方是有趣的。
A very common case is to walk a tree (or a graph, but trees are more common, in general). For example, a folder hierarchy: to list the files, you iterate on them. If you find a sub-directory, the function listing the files call itself with the new folder as argument. When coming back from listing this new folder (and its sub-folders!), it resumes its context, to the next file (or folder). Another concrete case is when drawing a hierarchy of GUI components: it is common to have containers, like panes, to hold components which can be panes too, or compound components, etc. The painting routine calls recursively the paint function of each component, which calls the paint function of all the components it holds, etc.
不确定我是否很清楚,但我喜欢展示现实世界中教材的使用,因为这是我过去偶然发现的东西。
Common Lisp中的简单递归示例:
MYMAP对列表中的每个元素应用一个函数。
1)空列表没有元素,所以我们返回空列表-()和NIL都是空列表。
2)将函数应用到第一个列表,对列表的其余部分调用MYMAP(递归调用),并将两个结果合并到一个新列表中。
(DEFUN MYMAP (FUNCTION LIST)
(IF (NULL LIST)
()
(CONS (FUNCALL FUNCTION (FIRST LIST))
(MYMAP FUNCTION (REST LIST)))))
让我们观察跟踪执行。在输入函数时,输出参数。在退出函数时,输出结果。对于每个递归调用,输出将按级别缩进。
这个例子对列表(1 2 3 4)中的每个数字调用SIN函数。
Command: (mymap 'sin '(1 2 3 4))
1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
| 3 Enter MYMAP SIN (3 4)
| | 4 Enter MYMAP SIN (4)
| | 5 Enter MYMAP SIN NIL
| | 5 Exit MYMAP NIL
| | 4 Exit MYMAP (-0.75680256)
| 3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)
这是我们的结果:
(0.841471 0.9092975 0.14112002 -0.75680256)
当使用递归解时,我总是尝试:
首先建立基本情况,即。 当n = 1的阶乘 试着想出一个一般的规则 对于其他情况
还有不同类型的递归解,分而治之的方法对分形和其他方法很有用。
如果你能先解决一些简单的问题,只是为了掌握窍门,这也会有帮助。一些例子是求解阶乘和生成第n个斐波那契数。
作为参考,我强烈推荐Robert Sedgewick的算法。
希望这能有所帮助。祝你好运。
要向一个六岁的孩子解释递归,首先要向一个五岁的孩子解释,然后再等一年。
实际上,这是一个有用的反例,因为递归调用应该更简单,而不是更难。向一个5岁的孩子解释递归就更难了,尽管你可以在0点停止递归,但你没有简单的解决方案来向一个0岁的孩子解释递归。
要使用递归解决一个问题,首先将其细分为一个或多个可以用相同方法解决的更简单的问题,然后当问题简单到无需进一步递归就可以解决时,您可以返回到更高的级别。
事实上,这是用递归方法来解决问题的递归定义。
递归
方法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...
}
}