理解递归 [英] 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.
嗯，我们能在代码中看到吗?
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.
让我们谈谈树.在计算机科学中，树是由节点组成的结构，其中每个节点都有一定数量的子节点，这些子节点也是节点，或者为空.二叉树是由具有正好两个子节点的节点组成的树，通常称为左"和右"；孩子们再次可以是节点，或者为空.root 是一个不是任何其他节点的子节点的节点.
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.
也许您已经预料到我将要做什么，并且想要查看一些代码?好的:
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 @ @
/ /
@@ @@
如果我们在根(值为 5 的节点)上调用 sumNode，我们将返回:
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 分支，以及两个几乎直接从我们的规范中编写的简单返回语句?
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 single 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 in 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.
我们不只是想随意打印，所以我们将向我们的函数传递一些要打印的东西.这将是一个带有 print(char) 函数的对象；我们不需要担心它是如何工作的，只需在调用 print 时，它会在某处打印一些东西.
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.
让我们在代码中看到:
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@
/
@@
我们要打印什么?
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.
我们设法按字母顺序打印一整棵树，只需知道如何按字母顺序打印单个节点.这只是(因为我们的树具有将值按字母顺序排列在后面值的左侧的特殊属性)知道在打印节点值之前打印左孩子，并在打印节点值之后打印右孩子.
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 to 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).
回想一下，在大多数语言中，运算符 ||("or") 当其第一个操作数为真时短路，一般递归函数为:
Recalling that in most languages, operator || ("or") short-circuits when its first operand is true, the general recursive function is:
void recurse() { doWeStop() || recurse(); }
Luc M 评论:
SO 应该为这种答案创建一个徽章.恭喜！
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.
这篇关于理解递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
