理解递归的算法

Question

我在学校很难理解递归。每当教授谈论这件事时，我似乎都明白了，但当我一个人尝试时，我的大脑就彻底崩溃了

我整晚都在试图解决河内的高塔问题，结果完全疯了。我的教科书只有大约30页的递归，所以不太有用。有人知道可以帮助澄清这个话题的书籍或资源吗

Answer 1

如果你想读一本简单地解释递归的书，可以看看道格拉斯·霍夫斯塔特（Douglas Hofstadter）的《哥德尔、埃舍尔、巴赫：永恒的金色辫子》，尤其是第5章。除了递归，它还以一种可以理解的方式很好地解释了计算机科学和数学中的一些复杂概念，一种解释建立在另一种解释之上。如果你以前没有太多接触过这类概念，这本书可能会让你大开眼界

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

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

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

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

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

为了求任意一个节点中的值之和，我们将把节点本身的值与它的左子节点（如果有的话）的值和它的右子节点（如果有的话）的值相加。现在回想一下，如果子节点不是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节点返回零

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

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

如果我们在根上调用sumNode（值为5的节点），我们将返回：

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

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示例不是尾部递归的，因为尽管我们做的最后一件事是递归右边的子对象，但在我们做之前，我们递归左边的子对象

事实上，我们调用子节点并将当前节点的值相加的顺序根本不重要，因为相加是可交换的

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

我们的树将有一个特殊的属性，即对于任何节点，其字符位于其左子节点持有的字符之后（按字母顺序），而位于其右子节点持有的字符之前（按字母顺序）

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

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

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

Answer 4

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

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

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

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页。”

你还推断，你应该从谷歌的“递归”结果页面开始，这也是计算机无法做到的。递归任务的完整描述还必须包括一个明确的起点：

“在网上了解有关递归的更多信息，直到你理解它，或者你从www.google.com/search？q=recursion开始最多阅读了10页。”

为了了解整个情况，我建议你尝试以下任何一本书：

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

Answer 5

实际上，使用递归可以降低手头问题的复杂性。你应用递归，直到你得到一个简单的基本情况，可以很容易地解决。有了这个，你可以解决最后一个递归步骤。有了这个，所有其他的递归步骤就可以解决你的原始问题了

Answer 6

这与其说是问题，不如说是抱怨。你对递归有更具体的问题吗？就像乘法一样，这不是人们经常写的东西

说到乘法，想想这个

问题:

什么是a*b

答复:

如果b是1，它就是a。 否则，它就是a+a*（b-1）

什么是a*（b-1）？请看上面的问题以了解解决方法