我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。

我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?


当前回答

我会用一个例子来解释。

你知道n!意味着什么?如果不是:http://en.wikipedia.org/wiki/Factorial

3! Is 1 times 2 times 3, which is 6

下面是一些伪代码

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

让我们试试吧:

factorial(3)

n是0吗?

no!

所以我们在递归中深入挖掘:

3 * factorial(3-1)

3 minus 1 is 2

2 == 0?

no!

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

1 == 0吗?

no!

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

0 == 0?

yes!

我们有一个小问题

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

我希望这对你有所帮助

其他回答

Ouch. I tried to figure out the Towers of Hanoi last year. The tricky thing about TOH is it's not a simple example of recursion - you have nested recursions which also change the roles of towers on each call. The only way I could get it to make sense was to literally visualize the movement of the rings in my mind's eye, and verbalize what the recursive call would be. I would start with a single ring, then two, then three. I actually ordered the game on the internet. It took me maybe two or three days of cracking my brains to get it.

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

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

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

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

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

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

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

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.

要理解递归,你只需要看看洗发水瓶上的标签:

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

这样做的问题是没有终止条件,递归将无限重复,或者直到洗发水或热水用完为止(外部终止条件,类似于吹你的堆栈)。

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