理解递归

Question

我在学校里理解递归时遇到了很大的困难。 每当教授谈论它时，我似乎都明白了，但当我自己尝试时，我就彻底震惊了。

我整晚都在尝试解决河内塔，结果完全让我大吃一惊。 我的教科书只有大约 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 循环中完成这个操作吗？

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

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

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

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

因此，为了对左子节点求和，我们会将子节点本身的值添加到其左子节点的值（如果有）以及右子节点的值（如果有）。

因此，为了对左子节点的左子节点的值求和，我们会将子节点本身的值添加到其左子节点的值（如果有）以及右子节点的值（如果有）。

也许您已经预料到我要讲的内容，并且想查看一些代码？ 好的：

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

这就是递归的力量。

---

上面的花瓶示例是尾递归的示例。 尾递归的意思是，在递归函数中，如果我们递归（即，如果我们再次调用该函数），那就是我们所做的最后一件事。

树的例子不是尾递归，因为尽管我们做的最后一件事是递归右子节点，但在此之前我们递归了左子节点。

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

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

我们的树有一个特殊的属性，对于任何节点，其字符都位于其左子节点持有的字符之后（按字母顺序）和之前（按字母顺序）其右孩子持有的角色。

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

我们不想随意打印，因此我们将向函数传递一些要打印的内容。 这将是一个带有 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”) 当其第一个操作数为 true 时短路，一般递归函数为：

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

Luc M 注释：

SO应该为这种答案创建一个徽章。 恭喜！

谢谢，吕克！ 但是，实际上，因为我编辑这个答案超过四次（添加最后一个示例，但主要是为了纠正拼写错误并完善它 - 在小型上网本键盘上打字很困难），我无法获得更多积分。 这在某种程度上阻止了我在未来的答案中投入那么多的精力。

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

Answer 2

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

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

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

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

如您所见，您已经进行递归操作很长时间了，没有出现任何问题。

你会继续做这项任务多久？ 永远直到你的大脑爆炸？ 当然不是，只要您相信自己已经完成了任务，您就会在给定点停下来。

当要求您“在网上查找有关递归的更多信息”时，无需指定这一点，因为您是人类，您可以自己推断。

计算机无法推断 jack，因此您必须包含一个明确的结尾：“在网上查找有关递归的更多信息，直到您理解它或最多阅读 10 页”。

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

“在网上查找有关递归的更多信息，直到您理解它或您已阅读最多 10 页并且开始位于 www.google.com/search?q=recursion"

至如果您了解了整个事情，我建议您尝试以下任何一本书：

• Common Lisp：符号计算的简要介绍。 这是对递归最可爱的非数学解释。
• 小阴谋家。

Answer 3

要了解递归，您所要做的就是查看洗发水瓶子的标签：

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

这样做的问题是没有终止条件，并且递归将无限期地重复，或者直到您用完洗发水或热水（外部）终止条件，类似于烧毁堆栈）。

Answer 4

如果您想要一本能够用简单的术语很好地解释递归的书，请看一下 Douglas Hofstadter 的哥德尔、埃舍尔、巴赫：永恒的金辫子，特别是第 5 章。除了递归之外它很好地以一种易于理解的方式解释了计算机科学和数学中的许多复杂概念，并且一种解释建立在另一种解释之上。 如果您以前没有太多接触过此类概念，那么这可能是一本非常令人兴奋的书。

Answer 5

这与其说是一个问题，不如说是一个抱怨。 您对递归有更具体的问题吗？ 就像乘法一样，人们很少写关于它的内容。

说到乘法，想一想这个。

问题：

a*b 是什么？

答案：

如果b为1，则为a。
否则，就是a+a*(b-1)。

什么是a*(b-1)？ 请参阅上面的问题以了解解决方法。

Answer 6

实际上，您使用递归来降低手头问题的复杂性。 您应用递归，直到达到可以轻松解决的简单基本情况。 这样你就可以解决最后的递归步骤。 这样所有其他递归步骤都会解决您原来的问题。

Answer 7

我认为这个非常简单的方法应该可以帮助您理解递归。 该方法将调用自身，直到某个条件为真，然后返回：

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

该函数将从您输入的第一个数字开始打印出所有数字，直到 0。因此：

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

基本上发生的事情是 writeNumbers(10) 将写入 10，然后调用 writeNumbers(9) 它将写入 9，然后调用 writeNumber(8) 等。直到 writeNumbers(1) 写入 1，然后调用 writeNumbers(0) 它将写入 0 但不会调用 writeNumbers(-1)；

此代码本质上与以下内容相同：

for(i=10; i>0; i--){
 write(i);
}

如果 for 循环的作用本质上相同，那么您可能会问为什么要使用递归。 好吧，当您必须嵌套 for 循环但不知道它们嵌套的深度时，您通常会使用递归。 例如，当从嵌套数组中打印项目时：

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

此函数可以采用一个可以嵌套 100 层的数组，而您编写 for 循环则需要将其嵌套 100 次：

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

如您所见，递归方法是好多了。

Answer 8

我将尝试用一个例子来解释它。

你知道什么！ 方法？ 如果没有：http://en.wikipedia.org/wiki/Factorial

3！ = 1 * 2 * 3 = 6

这里有一些伪代码

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

所以让我们尝试一下：

factorial(3)

n 是0 吗？

不！

所以我们用递归来更深入地挖掘：

3 * factorial(3-1)

3-1 = 2

是 2 == 0？

不！

所以我们更深入！
3 * 2 * 阶乘(2-1)
2-1 = 1

是 1 == 0 吗？

不！

所以我们更深入！
3 * 2 * 1 * 阶乘(1-1)
1-1 = 0

是 0 == 0 吗？

是的！

我们有一个简单的案例

，所以我们有
3 * 2 * 1 * 1 = 6

我希望对你有帮助

Answer 9

递归

方法A，调用方法A调用方法A。最终这些方法A中的一个不会调用并退出，但它是递归，因为有东西调用了它自己。

我想打印出硬盘驱动器上每个文件夹名称的递归示例：（在 c# 中）

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Answer 10

递归函数只是一个根据需要多次调用自身的函数。 如果您需要多次处理某些内容，但不确定实际需要多少次，那么它很有用。 在某种程度上，您可以将递归函数视为一种循环。 然而，就像循环一样，您需要指定进程被中断的条件，否则它将变得无限。

Answer 11

你用的是哪本书？

实际上很好的算法标准教科书是 Cormen 和 Cormen 。 里维斯特。 我的经验是它很好地教授了递归。

递归是编程中最难掌握的部分之一，虽然它确实需要本能，但它是可以学习的。 但它确实需要良好的描述、良好的示例和良好的插图。

而且，一般来说 30 页已经很多了，单一编程语言的 30 页令人困惑。 在从一般书籍中大致了解递归之前，不要尝试学习 C 或 Java 中的递归。

Answer 12

http://javabat.com 是一个有趣且令人兴奋的练习递归的地方。 他们的例子从相当简单的开始，到广泛的工作（如果你想深入的话）。 注意：他们的方法是通过练习来学习。 这是我编写的一个递归函数，用于简单地替换 for 循环。

for 循环：

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

这是做同样事情的递归。 （请注意，我们重载了第一个方法以确保它的使用方式与上面一样）。 我们还有另一种方法来维护索引（类似于上面 for 语句为您执行的方式）。 递归函数必须维护自己的索引。

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

总而言之，递归是编写更少代码的好方法。 在后面的 printBar 中，请注意我们有一个 if 语句。 如果达到了我们的条件，我们将退出递归并返回到前一个方法，该方法返回到前一个方法，依此类推。如果我发送了 printBar(8)，我会得到 ********。 我希望通过一个简单函数的示例来完成与 for 循环相同的事情，也许这会有所帮助。 不过，您可以在 Java Bat 中进行更多练习。

Answer 13

构建递归函数的真正数学方法如下：

1：假设您有一个对于 f(n-1) 是正确的函数，构建 f 使得 f(n) 是正确的。
2：建立f，使得f(1)是正确的。

这就是您如何证明该函数在数学上是正确的，它被称为归纳。 相当于在多个变量上有不同的基本情况，或更复杂的函数）。 这也相当于想象 f(x) 对于所有 x 都是正确的

现在举一个“简单”的例子。 构建一个函数，确定是否可以用 5 美分和 7 美分的硬币组合来制作 x 美分。 例如，2x5 + 1x7 可能有 17 美分，但不可能有 16 美分。

现在假设您有一个函数，可以告诉您是否可以创建 x 美分，只要 x < 名词 调用此函数can_create_coins_small。 想象如何创建 n 的函数应该相当简单。 现在构建您的函数：

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

这​​里的技巧是要认识到 can_create_coins 适用于 n 的事实，意味着您可以用 can_create_coins 替换 can_create_coins_small，给出：

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

最后要做的一件事是有一个基本情况来停止无限递归。 请注意，如果您尝试创造 0 美分，那么没有硬币也是可能的。 添加这个条件给出：

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

可以证明这个函数总是会返回，使用一种名为无限下降，但这里没有必要。 你可以想象 f(n) 只调用 n 的较低值，并且最终总是会达到 0。

要使用此信息来解决你的汉诺塔问题，我认为诀窍是假设你有一个移动 n-1 的函数平板电脑从a到b（对于任何a/b），尝试将n个表从a移动到b。

Answer 14

Common Lisp 中的简单递归示例：

MYMAP 将函数应用于列表中的每个元素。

1) 空列表没有元素，因此我们返回空列表 - () 和 NIL 都是空列表。

2) 将函数应用于第一个列表，对列表的其余部分调用 MYMAP（递归调用），并将两个结果合并到一个新列表中。

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

让我们看看跟踪的执行情况。 在输入函数时，将打印参数。 退出函数时，会打印结果。 对于每个递归调用，输出将按级别缩进。

此示例对列表中的每个数字 (1 2 3 4) 调用 SIN 函数。

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

这是我们的结果：

(0.841471 0.9092975 0.14112002 -0.75680256)

Answer 15

要向六岁的孩子解释递归，首先向五岁的孩子解释它，然后等待一年。

实际上，这是一个有用的反例，因为您的递归调用应该更简单，而不是更困难。 向五岁的孩子解释递归就更难了，虽然你可以在 0 处停止递归，但你没有简单的解决方案向零岁的孩子解释递归。

要使用递归解决问题，首先将其细分为一个或多个可以用相同方式解决的更简单问题，然后当问题足够简单而无需进一步递归即可解决时，您可以返回到更高的水平。

事实上，这是如何用递归解决问题的递归定义。

Answer 16

孩子们隐含地使用递归，例如：

去迪士尼世界的公路旅行

我们到了吗？（没有）

我们到了吗？（很快）

我们到了吗？（几乎...）

我们到了吗？（嘘）

我们到了吗？（!!!!!）

到了哪一步孩子睡着了...

这个倒计时函数是一个简单的例子：

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

适用于软件项目的霍夫施塔特定律也很重要。

根据乔姆斯基的说法，人类语言的本质是有限的大脑产生他认为无限的语法的能力。 他的意思不仅是我们可以说的内容没有上限，而且我们的语言拥有的句子数量没有上限，任何特定句子的大小也没有上限。 乔姆斯基声称，人类语言所有创造力的基础工具是递归：一个短语在同一类型的另一个短语中重复出现的能力。 如果我说“约翰的兄弟的房子”，我有一个名词“房子”，它出现在名词短语“兄弟的房子”中，而该名词短语出现在另一个名词短语“约翰的兄弟的房子”中。 这很有意义，也是人类语言的一个有趣的特性。

参考文献

• 递归和人类思想

Answer 17

在使用递归解决方案时，我总是尝试：

• 首先建立基本情况，即
  当阶乘解中 n = 1 时
• 尝试找出一般规则
  对于所有其他情况

，还有不同类型的递归解决方案，还有分而治之的方法，这对于分形和许多其他方法很有用。

如果您可以先解决更简单的问题以掌握窍门，也会有所帮助。 一些例子是求解阶乘并生成第 n 个斐波那契数。

作为参考，我强烈推荐 Robert Sedgewick 的算法。

希望有帮助。 祝你好运。

Answer 18

递归函数就像一个弹簧，每次调用时都会压缩一点。 在每个步骤中，您都将一些信息（当前上下文）放入堆栈中。 当到达最后一步时，弹簧被释放，立即收集所有值（上下文）！

不确定这个比喻是否有效......:-)

不管怎样，除了经典的例子（阶乘是最糟糕的例子，因为它效率低下并且容易扁平化，斐波那契，河内......），这些例子有点人为（我很少，如果永远，在真实的编程案例中使用它们），看看它真正在哪里使用是很有趣的。

一个非常常见的情况是遍历一棵树（或一张图，但一般来说，树更常见）。
例如，文件夹层次结构：要列出文件，您需要迭代它们。 如果找到子目录，列出文件的函数会调用自身，并以新文件夹作为参数。 当从列出这个新文件夹（及其子文件夹！）返回时，它会恢复其上下文，到下一个文件（或文件夹）。
另一个具体情况是绘制 GUI 组件的层次结构时：通常有容器（如窗格）来容纳也可以是窗格的组件，或复合组件等。绘制例程递归地调用每个组件的绘制函数，该函数调用它所拥有的所有组件的绘制函数等。

不确定我是否很清楚，但我喜欢展示教材的现实世界使用，因为这是我过去偶然发现的东西。

Answer 19

哎哟。 去年我试图弄清楚河内塔。 TOH 的棘手之处在于它不是一个简单的递归示例 - 您有嵌套递归，这也会改变每次调用时塔的角色。 我能让它有意义的唯一方法就是在我的脑海中逐字地想象环的运动，并用语言描述递归调用是什么。 我会从一个环开始，然后是两个，然后是三个。 我实际上是在互联网上订购了该游戏。 我大概花了两三天的时间才得到它。

Answer 20

想想工蜂。 它试图酿造蜂蜜。 它完成自己的工作，并期望其他工蜂来制造剩下的蜂蜜。 当蜂窝充满时，它就会停止。

将其视为魔法。 你有一个与你试图实现的函数同名的函数，当你给它子问题时，它会为你解决它，你唯一需要做的就是将你的部分的解决方案与它的解决方案集成起来给你。

例如，我们要计算一个列表的长度。 让我们用 magic_length 调用我们的函数 magic_length 和我们的神奇助手
我们知道，如果我们给出没有第一个元素的子列表，它会神奇地给我们子列表的长度。 那么我们唯一需要考虑的就是如何将这些信息与我们的工作结合起来。 第一个元素的长度是 1，magic_counter 给出子列表 n-1 的长度，因此总长度是 (n-1) + 1 -> 然而

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

这个答案是不完整的，因为我们没有考虑如果我们给出一个空列表会发生什么。 我们认为我们的列表总是至少有一个元素。 因此，我们需要考虑如果给定一个空列表并且答案显然是 0，答案应该是什么。因此，将此信息添加到我们的函数中，这称为基/边缘条件。

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length