algorithm - 理解递归

Question

就目前而言，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the help center为指导。




8年前关闭。




我在学校理解递归时遇到了很大的麻烦。每当教授谈论它时，我似乎都明白了，但是当我自己尝试时，它完全让我大吃一惊。

我整晚都在试图解决汉诺塔，完全让我大吃一惊。我的教科书只有大约 30 页的递归，所以它不是很有用。有没有人知道可以帮助澄清这个主题的书籍或资源？

Answer 1

如何清空装有五朵花的花瓶？

答案:如果花瓶不是空的，你取出一朵花
然后你清空一个装有四朵花的花瓶。

如何清空装有四朵花的花瓶？

答案:如果花瓶不是空的，你取出一朵花
然后你清空一个装有三朵花的花瓶。

如何清空装有三朵花的花瓶？

答案:如果花瓶不是空的，你取出一朵花
然后你清空一个装有两朵花的花瓶。

如何清空装有两朵花的花瓶？

答案:如果花瓶不是空的，你取出一朵花
然后你清空一个装有一朵花的花瓶。

如何清空装有一朵花的花瓶？

答案:如果花瓶不是空的，你取出一朵花
然后你清空一个没有花的花瓶。

没有花的花瓶怎么清空？

答案:如果花瓶不是空的，你取出一朵花
但花瓶是空的，所以你完成了。

那是重复的。让我们概括一下:

你如何清空一个装有 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 循环中完成吗？

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

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

想象一个节点，除了它的 child 之外，还有一个值，一个数字，并想象我们希望对某棵树中的所有值求和。

要对任何一个节点的值求和，我们会将节点本身的值与其左子节点的值(如果有)和右子节点的值(如果有)相加。现在回想一下，如果子节点不为空，它们也是节点。

因此，要对左 child 求和，我们会将 child 节点本身的值与其左 child 的值(如果有)和右 child 的值(如果有)相加。

因此，要对左 child 的左 child 的值求和，我们将 child 节点本身的值与其左 child 的值(如果有)和右 child 的值(如果有)相加。

也许您已经预料到我将要做什么，并希望看到一些代码？好的:

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):

     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

这就是递归的力量。

上面的花瓶例子是尾递归的一个例子。尾递归的全部意思是，在递归函数中，如果我们递归(也就是说，如果我们再次调用该函数)，那就是我们做的最后一件事。

树的例子不是尾递归的，因为即使我们做的最后一件事是递归右 child ，在我们这样做之前我们递归了左 child 。

事实上，我们调用子节点和添加当前节点值的顺序根本无关紧要，因为添加是可交换的。

现在让我们看一个顺序很重要的操作。我们将使用节点的二叉树，但这次持有的值将是一个字符，而不是一个数字。

我们的树将有一个特殊的属性，即对于任何节点，它的字符在(按字母顺序)其左 child 的字符之后，在(按字母顺序)其右 child 的字符之前。

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

我们不只是想随意打印，所以我们将向我们的函数传递一些要打印的东西。这将是一个带有 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(); } 

吕克M评论:

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

谢谢，卢克!但是，实际上，因为我编辑了这个答案四次以上(添加最后一个示例，但主要是为了更正拼写错误并润色它——在小型上网本键盘上打字很困难)，我无法获得更多分数.这有点让我不愿意在 future 的答案中付出那么多的努力。

请参阅我对此的评论: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699