我在学校理解递归方面遇到了很大麻烦.每当教授谈论它时,我似乎都能得到它,但是只要我自己尝试它就会彻底打动我的大脑.
我整晚都试图解决河内塔楼,并彻底打动了我的思绪.我的教科书在递归时只有大约30页,所以它不太有用.有谁知道可以帮助澄清这个主题的书籍或资源？
你如何清空一个装有五朵花的花瓶？
答:如果花瓶不是空的,你拿出一朵花然后倒空一个装有四朵花的花瓶.
你如何清空一个装有四朵花的花瓶？
答:如果花瓶不是空的,你取出一朵花然后倒空一个装有三朵花的花瓶.
你如何清空一个装有三朵花的花瓶？
答:如果花瓶不是空的,你拿出一朵花,然后你倒空一个装有两朵花的花瓶.
你如何清空一个装有两朵花的花瓶？
答:如果花瓶不是空的,你拿出一朵花,然后你倒空一个装有一朵花的花瓶.
你如何清空一个装有一朵花的花瓶？
答:如果花瓶不是空的,你拿出一朵花,然后你倒空一个不含花的花瓶.
你如何清空一个没有花的花瓶？
答:如果花瓶不是空的,你拿出一朵花,但花瓶是空的,所以你已经完成了.
这是重复的.让我们概括一下:
你如何清空一个装有N朵花的花瓶？
答:如果花瓶不是空的,你取出一朵花然后倒空装有N-1花的花瓶.
嗯,我们能在代码中看到吗？
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
嗯,难道我们不能在for循环中做到这一点吗？
为什么,是的,递归可以用迭代替换,但通常递归更优雅.
我们来谈谈树木.在计算机科学中,树是由节点组成的结构,其中每个节点具有一些也是节点的子节点,或者为空.一个二叉树是由它们拥有完全节点树2个子女,通常被称为"左"和"右"; 孩子们可以是节点,也可以是null.一个根本的是,没有任何其他节点的子节点.
想象一下,除了子节点之外,节点还有一个值,一个数字,并想象我们希望对某些树中的所有值求和.
为了对任何一个节点中的值求和,我们将节点本身的值添加到其左子节点的值(如果有)以及其右子节点的值(如果有).现在回想一下,如果孩子们不是空的,他们也是节点.
因此,为了对左子节点求和,我们将子节点本身的值添加到其左子节点的值(如果有)以及其右子节点的值(如果有).
因此,为了对左孩子的左孩子的值求和,我们将子节点本身的值添加到其左子元素的值(如果有)和其右子元素的值(如果有).
也许你已经预料到我要去哪里了,并希望看到一些代码？好:
struct node {
node* left;
node* right;
int value;
} ;
int sumNode( node* root ) {
// if there is no tree, its sum is zero
if( root == null ) {
return 0 ;
} else { // there is a tree
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
}
}
请注意,我们只是使子节点的递归函数返回零,而不是显式测试子节点以查看它们是否为null或节点.
所以说我们有一个看起来像这样的树(数字是值,斜线指向子节点,@表示指针指向null):
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
如果我们在根(值为5的节点)上调用sumNode,我们将返回:
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
让我们扩展它.我们到处看到sumNode,我们将用return语句的扩展替换它:
sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ sumNode( node-with-value-1 )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + sumNode(null ) + sumNode( null )
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ sumNode( node-with-value-3 ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + sumNode(null ) + sumNode( null ) ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 + 0 + 0 ;
return 5 + 4
+ 2 + 0 + 0
+ 1 + 0 + 0
+ 3 ;
return 5 + 4
+ 2 + 0 + 0
+ 1
+ 3 ;
return 5 + 4
+ 2
+ 1
+ 3 ;
return 5 + 4
+ 3
+ 3 ;
return 5 + 7
+ 3 ;
return 5 + 10 ;
return 15 ;
现在看看我们如何通过将其视为复合模板的重复应用来征服任意深度和"分支"的结构？每次通过我们的sumNode函数,我们只处理一个节点,使用单个if/then分支,以及两个简单的返回语句,几乎直接从我们的规范中编写了这些字符？
How to sum a node: If a node is null its sum is zero otherwise its sum is its value plus the sum of its left child node plus the sum of its right child node
这就是递归的力量.
上面的花瓶示例是尾递归的示例.所有尾递归意味着在递归函数中,如果我们递归(也就是说,如果我们再次调用函数),那就是我们做的最后一件事.
树的例子不是尾递归的,因为尽管我们做的最后一件事是递归正确的孩子,但在我们这样做之前,我们会对左孩子进行递归.
实际上,我们调用子节点的顺序和添加当前节点的值根本没有关系,因为加法是可交换的.
现在让我们看看订单重要的操作.我们将使用节点的二叉树,但这次保持的值将是一个字符,而不是一个数字.
我们的树将有一个特殊的属性,对于任何节点,它的性质来之后(排名不分先后)通过其左子并举行了字符之前(排名不分先后)通过其右孩子举行的字符.
我们想要做的是打印树是按字母顺序排列的.考虑到树的特殊属性,这很容易做到.我们只打印左边的孩子,然后是节点的角色,然后是右边的孩子.
我们不仅仅想要打印,因此我们将传递我们的函数来打印.这将是一个具有print(char)函数的对象; 我们不需要担心它是如何工作的,只是当调用打印时,它会打印某些东西.
我们在代码中看到:
struct node {
node* left;
node* right;
char value;
} ;
// don't worry about this code
class Printer {
private ostream& out;
Printer( ostream& o ) :out(o) {}
void print( char c ) { out << c; }
}
// worry about this code
int printNode( node* root, Printer& printer ) {
// if there is no tree, do nothing
if( root == null ) {
return ;
} else { // there is a tree
printNode( root->left, printer );
printer.print( value );
printNode( root->right, printer );
}
Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );
除了现在重要的操作顺序之外,这个例子说明我们可以将事物传递给递归函数.我们唯一要做的就是确保在每次递归调用时,我们继续传递它.我们将一个节点指针和一个打印机传递给该函数,并在每次递归调用时,我们将它们"向下"传递.
现在,如果我们的树看起来像这样:
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
我们会打印什么？
From k, we go left to
h, where we go left to
a, where we go left to
null, where we do nothing and so
we return to a, where we print 'a' and then go right to
null, where we do nothing and so
we return to a and are done, so
we return to h, where we print 'h' and then go right to
j, where we go left to
i, where we go left to
null, where we do nothing and so
we return to i, where we print 'i' and then go right to
null, where we do nothing and so
we return to i and are done, so
we return to j, where we print 'j' and then go right to
null, where we do nothing and so
we return to j and are done, so
we return to h and are done, so
we return to k, where we print 'k' and then go right to
n where we go left to
null, where we do nothing and so
we return to n, where we print 'n' and then go right to
null, where we do nothing and so
we return to n and are done, so
we return to k and are done, so we return to the caller
所以,如果我们只是看看我们印刷的线条:
we return to a, where we print 'a' and then go right to
we return to h, where we print 'h' and then go right to
we return to i, where we print 'i' and then go right to
we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
we return to n, where we print 'n' and then go right to
我们看到我们打印了"ahijkn",这确实按字母顺序排列.
我们设法按字母顺序打印整个树,只需知道如何按字母顺序打印单个节点.这只是(因为我们的树具有在按字母顺序排列的值的左侧排序值的特殊属性)知道在打印节点的值之前打印左子节点,并且在打印节点的值之后打印右子节点.
这就是递归的力量:能够通过只知道如何做整体的一部分(以及知道何时停止递归)来完成整个事情.
回顾在大多数语言中,运算符|| ("或")在第一个操作数为真时发生短路,一般递归函数为:
void recurse() { doWeStop() || recurse(); }
Luc M评论:
所以应该为这种答案创建徽章.恭喜!
谢谢,吕克!但是,实际上,因为我编辑了这个答案超过四次(添加最后一个例子,但主要是为了纠正错别字并打磨它 - 在一个小小的上网本键盘上输入很难),我无法获得更多的积分.这有点使我无法在未来的答案中投入太多精力.
请参阅我的评论:https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699
你的大脑爆炸了,因为它进入了无限的递归.这是一个常见的初学者错误.
信不信由你,你已经理解了递归,你只是被一个普通但错误的隐喻所拖累,一个功能:一个带有进出的东西的小盒子.
思考而不是任务或程序,例如"在网上找到更多关于递归的信息".这是递归的,你没有问题.要完成此任务,您可以:
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页 ".
您还推断出您应该从Google的结果页面开始"递归",并且这也是计算机无法做到的事情.我们的递归任务的完整描述还必须包含一个明确的起点:
"了解更多关于网上递归的信息,直到您了解它,或者您已经阅读了最多10页并从www.google.com/search?q=recursion开始 "
为了理解整件事,我建议你试试这些书:
Common Lisp:对符号计算的温和介绍.这是递归的最可爱的非数学解释.
小阴谋家.
要了解递归,您只需查看洗发水瓶的标签即可:
function repeat()
{
rinse();
lather();
repeat();
}
这个问题是没有终止条件,递归会无限期地重复,或者直到你用完洗发水或热水(外部终止条件,类似于吹你的堆栈).
如果你想要一本能用简单的术语解释递归的书,请看看道格拉斯霍夫斯塔特的哥德尔,埃舍尔,巴赫:永恒的金色辫子,特别是第5章.除了递归,它还能很好地解释计算机科学和数学中的一些复杂概念以可理解的方式,一种解释建立在另一种上.如果您之前没有太多接触过这些概念,那么它可能是一本非常令人兴奋的书.
这更像是一个抱怨,而不是一个问题.你有关于递归的更具体的问题吗？就像乘法一样,这不是人们写的很多东西.
说到乘法,想一想.
题:
什么是*b？
回答:
如果b是1,那就是a.否则,它是+ a*(b-1).
什么是*(b-1)？请参阅上述问题以获得解决方法.
我认为这个非常简单的方法可以帮助您理解递归.该方法将调用自身直到某个条件为真,然后返回:
function writeNumbers( aNumber ){
write(aNumber);
if( aNumber > 0 ){
writeNumbers( aNumber - 1 );
}
else{
return;
}
}
此功能将打印出您要输入的第一个数字中的所有数字,直至为0.
writeNumbers( 10 ); //This wil write: 10 9 8 7 6 5 4 3 2 1 0 //and then stop because aNumber is no longer larger then 0
低音发生的是writeNumbers(10)将写入10然后调用writeNumbers(9),它将写入9然后调用writeNumber(8)等.直到writeNumbers(1)写入1然后调用writeNumbers(0)将写入0对接不会调用writeNumbers(-1);
此代码基本上与以下内容相同:
for(i=10; i>0; i--){
write(i);
}
那么为什么使用你可能会问的递归,如果for循环基本上是相同的.那么你大多使用递归,你必须嵌套for循环但不知道它们嵌套的深度.例如,从嵌套数组中打印出项目时:
var nestedArray = Array('Im a string',
Array('Im a string nested in an array', 'me too!'),
'Im a string again',
Array('More nesting!',
Array('nested even more!')
),
'Im the last string');
function printArrayItems( stringOrArray ){
if(typeof stringOrArray === 'Array'){
for(i=0; i
这个函数可以采用一个可以嵌套到100个级别的数组,而编写for循环则需要将它嵌套100次:
for(i=0; i
正如您所看到的,递归方法要好得多.
7> 小智..：
实际上,您使用递归来降低手头问题的复杂性.您应用递归直到达到可以轻松解决的简单基本情况.有了这个,你可以解决最后一个递归步骤.通过这一切所有其他递归步骤直到你原来的问题.
8> Sekhat..：
递归
方法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...
}
}
9> Zoran Zaric..：
我将尝试用一个例子来解释它.
你知道吗!手段？如果没有:http://en.wikipedia.org/wiki/Factorial
3!= 1*2*3 = 6
这里有一些伪代码
function factorial(n) {
if (n==0) return 1
else return (n * factorial(n-1))
}
所以让我们试试吧:
factorial(3)
是n 0？
没有!
所以我们通过递归深入挖掘:
3 * factorial(3-1)
3-1 = 2
是2 == 0？
没有!
所以我们走得更深!3*2*阶乘(2-1)2-1 = 1
是1 == 0？
没有!
所以我们走得更深!3*2*1*阶乘(1-1)1-1 = 0
是0 == 0？
是!
我们有一个微不足道的案例
所以我们有3*2*1*1 = 6
我希望能帮助你
京公网安备 11010802040832号 | 京ICP备19059560号-6 