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

1:假设你有一个函数对f(n-1)是正确的，构造f使f(n)是正确的。 2:构造f，使得f(1)是正确的。

This is how you can prove that the function is correct, mathematically, and it's called Induction. It is equivalent to have different base cases, or more complicated functions on multiple variables). It is also equivalent to imagine that f(x) is correct for all x Now for a "simple" example. Build a function that can determine if it is possible to have a coin combination of 5 cents and 7 cents to make x cents. For example, it's possible to have 17 cents by 2x5 + 1x7, but impossible to have 16 cents. Now imagine you have a function that tells you if it's possible to create x cents, as long as x < n. Call this function can_create_coins_small. It should be fairly simple to imagine how to make the function for n. Now build your function: 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; } The trick here is to realize that the fact that can_create_coins works for n, means that you can substitute can_create_coins for can_create_coins_small, giving: 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; } One last thing to do is to have a base case to stop infinite recursion. Note that if you are trying to create 0 cents, then that is possible by having no coins. Adding this condition gives: 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; } It can be proven that this function will always return, using a method called infinite descent, but that isn't necessary here. You can imagine that f(n) only calls lower values of n, and will always eventually reach 0. To use this information to solve your Tower of Hanoi problem, I think the trick is to assume you have a function to move n-1 tablets from a to b (for any a/b), trying to move n tables from a to b.

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

信不信由你，你已经理解了递归，你只是被一个常见的，但错误的函数比喻拖了下来:一个小盒子，里面有东西进进出出。

而不是考虑一个任务或过程，比如“在网上找到更多关于递归的知识”。这是递归的，没有问题。要完成这个任务，你可以:

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

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

“在网上找到更多关于递归的知识，直到你理解它，或者你已经阅读了最多10页，并从www.google.com/search?q=recursion开始”

要想全面了解，我建议你试试下面这些书:

普通Lisp:符号计算的简单介绍。这是对递归最可爱的非数学解释。 小阴谋家。

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中进行更多的练习。

你如何倒空一个装有五朵花的花瓶?

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

你如何倒空一个装有四朵花的花瓶?

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

你如何倒空一个装有三朵花的花瓶?

答:如果花瓶不是空的，你就拿出一朵花 然后你把装着两朵花的花瓶倒空。

你如何倒空一个装有两朵花的花瓶?

答:如果花瓶不是空的，你就拿出一朵花 然后你把只装了一朵花的花瓶倒空。

你如何清空只装了一朵花的花瓶?

答:如果花瓶不是空的，你就拿出一朵花 然后你倒空了一个没有花的花瓶。

你怎么倒空一个没有花的花瓶?

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

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

你如何倒空一个装有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循环中做这个吗?

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

让我们来谈谈树。在计算机科学中，树是由节点组成的结构，其中每个节点都有一定数量的子节点，这些子节点也是节点或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):

     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")在第一个操作数为真时短路，一般递归函数为:

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

Luc M评论道:

SO应该为这种回答创建一个徽章。恭喜你!

谢谢,吕克·!但实际上，因为我编辑了不止四次这个答案(为了添加最后一个例子，但主要是为了纠正错字和润色——在一个小小的上网本键盘上打字很困难)，我无法从这个答案中获得更多的分数。这在一定程度上阻碍了我在未来的答案上花那么多精力。

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

想想工蜂。它试着酿蜂蜜。它完成了自己的工作，并期待其他工蜂来酿造剩下的蜂蜜。蜂房满了，蜂房就停了。

把它想象成魔法。你有一个与你要实现的函数同名的函数，当你给它子问题时，它就会帮你解决它，你唯一需要做的就是把你的部分的解与它给你的解集成起来。

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

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

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

实际上，这是一个有用的反例，因为递归调用应该更简单，而不是更难。向一个5岁的孩子解释递归就更难了，尽管你可以在0点停止递归，但你没有简单的解决方案来向一个0岁的孩子解释递归。

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

事实上，这是用递归方法来解决问题的递归定义。