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

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.

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

当使用递归解时，我总是尝试:

首先建立基本情况，即。 当n = 1的阶乘 试着想出一个一般的规则 对于其他情况

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

如果你能先解决一些简单的问题，只是为了掌握窍门，这也会有帮助。一些例子是求解阶乘和生成第n个斐波那契数。

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

希望这能有所帮助。祝你好运。

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

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

例如，我们想计算一个列表的长度。让我们用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

如果你想要一本很好地用简单的术语解释递归的书，可以看看Gödel，埃舍尔·巴赫:道格拉斯·霍夫施塔特的《永恒的金辫子》，特别是第五章。除了递归，它还能很好地以一种可理解的方式解释计算机科学和数学中的许多复杂概念，一个解释建立在另一个解释的基础上。如果你以前没有接触过这类概念，这可能是一本非常令人兴奋的书。

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

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

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

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:符号计算的简单介绍。这是对递归最可爱的非数学解释。 小阴谋家。