了解递归 [英] Understanding recursion
问题描述
我在各大无法理解的递归的学校。每当教授在谈论它，我好像得到它，但只要我试试我自己就完全吹我的大脑。
I'm having major trouble understanding recursion at school. Whenever the professor is talking about it, I seem to get it but as soon as I try it on my own it completely blows my brains.
我试图解决的的汉诺塔的整夜，完全吹我的脑海里。我的书只有大约30递归页，所以它不是太有用。有谁知道书或资源，可以帮助澄清这个主题吗？
I was trying to solve Towers of Hanoi all night and completely blew my mind. My textbook has only about 30 pages in recursion so it is not too useful. Does anyone know of books or resources that can help clarify this topic?
推荐答案
你怎么清空包含五个一盆花？
How do you empty a vase containing five flowers?
答：如果这个花瓶不是空的，你把一朵花 然后清空包含四个花的花瓶。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing four flowers.
你怎么清空包含四个花的花瓶？
How do you empty a vase containing four flowers?
答：如果这个花瓶不是空的，你把一朵花 然后清空包含三个一盆花。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing three flowers.
你怎么清空包含三个花的花瓶？
How do you empty a vase containing three flowers?
答：如果这个花瓶不是空的，你把一朵花 然后清空包含两个花的花瓶。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing two flowers.
你怎么清空包含两个花的花瓶？
How do you empty a vase containing two flowers?
答：如果这个花瓶不是空的，你把一朵花 然后清空包含一个花的花瓶。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing one flower.
你怎么清空包含一个花的花瓶？
How do you empty a vase containing one flower?
答：如果这个花瓶不是空的，你把一朵花 然后你空不包含花的花瓶。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing no flowers.
你怎么清空不含花的花瓶？
How do you empty a vase containing no flowers?
答：如果这个花瓶不是空的，你把一朵花 但是花瓶是空的，所以你就大功告成了。
Answer: if the vase is not empty, you take out one flower but the vase is empty so you're done.
这是重复的。让我们来概括它：
That's repetitive. Let's generalize it:
你怎么清空包含一个花瓶的 N 的花？
How do you empty a vase containing N flowers?
答：如果这个花瓶不是空的，你把一朵花 然后你空花瓶包含的 N-1 的鲜花。
Answer: if the vase is not empty, you take out one flower and then you empty a vase containing N-1 flowers.
嗯，我们可以看到，在code？
Hmm, can we see that in code?
void emptyVase( int flowersInVase ) {
if( flowersInVase > 0 ) {
// take one flower and
emptyVase( flowersInVase - 1 ) ;
} else {
// the vase is empty, nothing to do
}
}
嗯，不可能，我们刚刚做了一个for循环？
Hmm, couldn't we have just done that in a for loop?
为什么是的，递归可以用迭代更换，但往往递归是更优雅。
Why yes, recursion can be replaced with iteration, but often recursion is more elegant.
让我们来谈谈树木。在计算机科学中，树的是由节点的，其中每个节点都有的孩子，是一些数量也节点或空的结构。 A 二叉树的是由具有节点树完全的两个的孩子，通常被称为左和右;再次，孩子们可以在节点，或者为null。 A 根的是一个节点，是不是任何其他节点的孩子。
Let's talk about trees. In computer science, a tree is a structure made up of nodes, where each node has some number of children that are also nodes, or null. A binary tree is a tree made of nodes that have exactly two children, typically called "left" and "right"; again the children can be nodes, or null. A root is a node that is not the child of any other node.
想象一下一个节点，它除了孩子，有一个价值，一个数字，假设我们希望总结一些树中的所有值。
Imagine that a node, in addition to its children, has a value, a number, and imagine that we wish to sum all the values in some tree.
要求和值中的任何一个节点，我们将节点本身的值添加到它的左子的值，如果有的话，它的右子的，该值如果有的话。现在回想一下，孩子们，如果他们不为空，也都是节点。
To sum value in any one node, we would add the value of node itself to the value of its left child, if any, and the value of its right child, if any. Now recall that the children, if they're not null, are also nodes.
所以，总结左子，我们如果有子节点本身的价值添加到其左子的价值，以及其右孩子的，价值（如有）。
So to sum the left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.
因此归结左子的左子的值，我们将子节点本身的值添加到它的左子的值，如果有的话，它的右孩子的，值，如果有的话。
So to sum the value of the left child's left child, we would add the value of child node itself to the value of its left child, if any, and the value of its right child, if any.
也许你已经期待我要去哪里这个问题，并希望看到一些code？ OK：
Perhaps you've anticipated where I'm going with this, and would like to see some code? OK:
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 ) ;
}
}
的通知，而不是明确地测试的孩子，看看他们是否为空或节点，我们只是做了递归函数返回零空节点。
Notice that instead of explicitly testing the children to see if they're null or nodes, we just make the recursive function return zero for a null node.
所以说我们有一棵树，看起来像这样（的数字值，斜线指向孩子，和@意味着指针指向空）：
So say we have a tree that looks like this (the numbers are values, the slashes point to children, and @ means the pointer points to null):
5
/ \
4 3
/\ /\
2 1 @ @
/\ /\
@@ @@
如果我们呼吁sumNode根（值为5点），我们将返回：
If we call sumNode on the root (the node with value 5), we will return:
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;
让我们展开到位。我们到处看到sumNode，我们将与return语句的扩展替代它：
Let's expand that in place. Everywhere we see sumNode, we'll replace it with the expansion of the return statement:
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分支，两个简单的return语句，几乎写道themsleves，直接从我们的规范？
Now see how we conquered a structure of arbitrary depth and "branchiness", by considering it as the repeated application of a composite template? each time through our sumNode function, we dealt with only a single node, using a singe if/then branch, and two simple return statements that almost wrote themsleves, directly from our specification?
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
就是的递归的力量。
花瓶上面的例子是的尾递归的一个例子。所有这一切的尾递归的意思是，在递归函数，如果我们递归（也就是说，如果我们再次调用的函数），这是我们做的最后一件事。
The vase example above is an example of tail recursion. All that tail recursion means is that in the recursive function, if we recursed (that is, if we called the function again), that was the last thing we did.
树的例子是不是尾递归，因为即使我们这样做最后一件事是递归的右孩子，在我们这样做，我们递归左子。
The tree example was not tail recursive, because even though that last thing we did was to recurse the right child, before we did that we recursed the left child.
事实上，在此我们呼吁孩子们，并添加了当前节点的值没有关系可言，因为除了是可交换的顺序。
In fact, the order in which we called the children, and added the current node's value didn't matter at all, because addition is commutative.
现在让我们来看看一个操作，其中顺序很重要。我们将使用节点的二叉树，但这次举办的值是一个字符，而不是数量。
Now let's look at an operation where order does matter. We'll use a binary tree of nodes, but this time the value held will be a character, not a number.
我们的树将有一个特殊的属性，对于任何节点，它的性质来的在的（排名不分先后）持有其左子和字符的在的（以排名不分先后）其右孩子举行的字符。
Our tree will have a special property, that for any node, its character comes after (in alphabetical order) the character held by its left child and before (in alphabetical order) the character held by its right child.
我们想要做的是打印的树是按字母顺序排列。这是很容易做到，因为树的特殊属性。我们只是打印左子，那么该节点的角色，然后右键孩子。
What we want to do is print the tree is alphabetical order. That's easy to do, given the tree special property. We just print the left child, then the node's character, then right child.
我们不只是想打印慎之又慎，因此我们将通过我们的一些功能上进行打印。这将是一个对象，打印（字符）的功能;我们并不需要担心它是如何工作的，只是在打印时被调用，它会打印一些东西，某个地方。
We don't just want to print willy-nilly, so we'll pass our function something to print on. This will be an object with a print( char ) function; we don't need to worry about how it works, just that when print is called, it'll print something, somewhere.
让我们来看看，在code：
Let's see that in code:
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 );
在除了操作现在无所谓的顺序，这个例子说明，我们可以通过东西放进一个递归函数。我们必须做的唯一一件事就是确保每个递归调用，我们将继续通过它一起。我们通过在一个节点指针和打印机的功能，并在每次递归调用，我们通过他们的下降。
In addition to the order of operations now mattering, this example illustrates that we can pass things into a recursive function. The only thing we have to do is make sure that on each recursive call, we continue to pass it along. We passed in a node pointer and a printer to the function, and on each recursive call, we passed them "down".
现在，如果我们的树看起来是这样的：
Now if our tree looks like this:
k
/ \
h n
/\ /\
a j @ @
/\ /\
@@ i@
/\
@@
我们会怎样打印？
What will we print?
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
因此，如果我们只看系我们打印：
So if we just look at the lines were we printed:
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，这确实是按字母顺序排列。
We see we printed "ahijkn", which is indeed in alphabetical order.
我们设法打印整个树，按字母顺序排列，只是知道如何打印按字母顺序排列的单个节点。这只是（因为我们树起了订购价值，按字母顺序后值的左边的特殊属性）打印节点的值之后知道打印节点的值之前打印的左子，和TTO打印正确的孩子。
We manage to print an entire tree, in alphabetical order, just by knowing how to print a single node in alphabetical order. Which was just (because our tree had the special property of ordering values to the left of alphabetically later values) knowing to print the left child before printing the node's value, and tto print the right child after printing the node's value.
和这是的递归的力量：能够在仅知道该怎么做了整体的一部分（并知道何时停止递归）做整个事情
And that's the power of recursion: being able to do whole things by knowing only how to do a part of the whole (and knowing when to stop recursing).
回顾，在大多数语言中，运营商|| （或）短路时，它的第一个操作数是真实的，一般的递归函数是：
Recalling that in most languages, operator || ("or") short-circuits when its first operand is true, the general recursive function is:
void recurse() { doWeStop() || recurse(); }
吕克·M评论：
Luc M comments:
所以要创建一个徽章这样的答案。恭喜！
SO should create a badge for this kind of answer. Congratulations!
谢谢，吕克！但是，实际上，因为我编辑这个答案的四倍以上（添加的最后一个例子，但主要是纠正错别字，把它擦亮 - 打字上网本的小键盘上很难），我不能获得任何更多的积分。这在一定程度从投入尽可能多的精力投入到未来的答案，鼓励我。
Thanks, Luc! But, actually, because I edited this answer more than four times (to add the last example, but mostly to correct typos and polish it -- typing on a tiny netbook keyboard is hard), I can't get any more points for it. Which somewhat discourages me from putting as much effort into future answers.
请参阅我的意见在这里说：<一href="http://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699">http://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699
See my comment here on that: http://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699
这篇关于了解递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
