理解递归

Question

我在学校里很难理解递归。每当教授在谈论这个问题时，我似乎都能理解，但只要我自己尝试，它就会让我彻底崩溃。

我整晚都在试图解决河内的塔楼问题，完全让我大吃一惊。我的课本只有大约30页的递归，所以不太有用。是否有人知道有助于澄清这一主题的书籍或资源？

Answer 1

你的大脑爆炸了，因为它进入了无限的循环。这是初学者常犯的错误。

信不信由你，你已经了解递归了，你只是被一个普通但错误的函数隐喻拖累了：一个小盒子，里面装着进出的东西。

思考而不是一个任务或过程，比如“在网络上找到更多关于递归的信息”。这是递归的，你没有问题。要完成此任务，您可以：

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=递归“

为了搞清整件事，我建议你试试这些书中的任何一本：

• Common Lisp：符号计算的温和介绍。这是递归最简洁的非数学解释。
• 小阴谋家。

Answer 2

你怎么把一个装有五朵花的花瓶倒空？

回答：如果花瓶不是空的，你就拿出一朵花 然后你倒空了一个花瓶，里面有四朵花。

你怎么把一个装有四朵花的花瓶倒空？

回答：如果花瓶不是空的，你就拿出一朵花 然后你倒空了一个花瓶，里面有三朵花。

一个花瓶里有三朵花，你怎么倒空的？

回答：如果花瓶不是空的，你就拿出一朵花 然后你倒空了一个花瓶，里面有两朵花。

你怎么把一个装有两朵花的花瓶倒空？

回答：如果花瓶不是空的，你就拿出一朵花 然后你清空一个花瓶，里面有一朵花。

你怎么把一个花瓶里的一朵花掏空？

回答：如果花瓶不是空的，你就拿出一朵花 然后你清空一个没有花的花瓶。

你怎么把没有花的花瓶倒空？

回答：如果花瓶不是空的，你就拿出一朵花 但花瓶是空的，所以你完了。

这是重复的。让我们概括一下：

你如何清空一个花瓶，里面有花？

回答：如果花瓶不是空的，你就拿出一朵花 然后你清空一个花瓶，里面有N-1花。

嗯，我们能在代码中看到吗？

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

嗯，难道我们就不能在一个循环中这样做吗？

是的，递归可以用迭代来代替，但通常递归更优雅。

我们来谈谈树吧。在计算机科学中，树是由节点组成的结构，其中每个节点都有一些子节点，这些子节点也是节点或空节点。二叉树是由两个子节点组成的树，通常称为“左”和“右”；子节点可以是节点，也可以是空的。根节点不是任何其他节点的子节点。

假设一个节点，除了它的子节点之外，还有一个值，一个数字，并假设我们希望将某个树中的所有值相加。

为了求任意一个节点的值之和，我们将节点本身的值添加到其左子节点的值（如果有）和右子节点的值（如果有）。现在回想一下，如果子节点不是空的，那么它们也是节点。

所以为了求左子节点的和，我们将把子节点本身的值加到左子节点的值（如果有的话）和右子节点的值（如果有的话）上。

所以为了求左子节点的左子节点的值之和，我们将子节点本身的值添加到其左子节点的值（如果有的话）和其右子节点的值（如果有的话）中。

也许你已经预料到了我要做什么，想看看代码吗？好的：

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 ) ;
  }
}

注意，不是显式地测试子节点以查看它们是空的还是节点的，我们只是让递归函数为空节点返回零。

假设我们有一个这样的树（数字是值，斜杠指向子级，@表示指针指向空值）：

     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分支，以及两个简单的返回语句，它们几乎直接从我们的规范中编写了sleves？

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

这就是递归的力量。

---

上面的花瓶示例是尾部递归的示例。尾部递归意味着在递归函数中，如果我们递归（也就是说，如果我们再次调用函数），那是我们最后做的事情。

tree示例不是tail recursive，因为即使我们做的最后一件事是递归右边的子元素，在我们递归左边的子元素之前。

实际上，调用子节点并添加当前节点值的顺序根本不重要，因为加法是可交换的。

现在让我们来看一个订单确实重要的操作。我们将使用节点的二叉树，但这次保存的值将是字符，而不是数字。

我们的树将有一个特殊的属性，对于任何节点，它的字符在其左子节点的字符后出现，在其右子节点的字符前出现。

我们要做的是按字母顺序打印树。考虑到树的特殊属性，这很容易做到。我们只打印左子节点的字符，然后打印右子节点的字符。

我们不只是想随意地打印，所以我们将传递一些要打印的函数。这将是一个带有print（char）函数的对象；我们不需要担心它是如何工作的，只要在调用print时，它会在某个地方打印一些东西。

让我们在代码中看到：

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”，确实是按字母顺序排列的。

我们设法按字母顺序打印整个树，只需知道如何按字母顺序打印单个节点。这只是（因为我们的树具有将值按字母顺序排列到后面的值左边的特殊属性）知道在打印节点值之前打印左边的子节点，在打印节点值之后打印右边的子节点。

这就是递归的力量：通过只知道如何做整体的一部分（以及知道何时停止递归）就能完成所有的事情。

回顾在大多数语言中，运算符| |（“or”）在其第一个操作数为真时短路，一般的递归函数是：

void recurse() { doWeStop() || recurse(); } 

Luc M评论：

SO should create a badge for this kind of answer. Congratulations!

谢谢，卢克！但是，事实上，因为我编辑了这个答案四次以上（加上最后一个例子，但主要是为了纠正拼写错误和润色它——在一个小小的上网本键盘上打字是很困难的），所以我再也得不到分数了。这在一定程度上阻碍了我在未来的答案中投入同样多的精力。

请看我的评论：https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Answer 3

要了解递归，你只需看看你的洗发水瓶上的标签：

function repeat()
{
   rinse();
   lather();
   repeat();
}

问题是没有终止条件，递归将无限期地重复，或者直到洗发水或热水用完（外部终止条件，类似于吹堆栈）。