我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
当前回答
要理解递归,你只需要看看洗发水瓶上的标签:
function repeat()
{
rinse();
lather();
repeat();
}
这样做的问题是没有终止条件,递归将无限重复,或者直到洗发水或热水用完为止(外部终止条件,类似于吹你的堆栈)。
其他回答
实际上,使用递归是为了降低手头问题的复杂性。你应用递归,直到你达到一个简单的基本情况,可以很容易地解决。这样就可以解决最后一个递归步骤。用这些递归步骤就可以解决最初的问题。
子函数隐式地使用递归,例如:
去迪士尼乐园自驾游
我们到了吗?(没有) 我们到了吗?(很快) 我们到了吗?(快了……) 我们到了吗? 我们到了吗?(!!!!!)
这时孩子就睡着了……
这个倒数函数是一个简单的例子:
倒计时()函数 { 返回(参数[0]> 0 ? ( Console.log(参数[0]),倒计时(参数[0]- 1)): “完成” ); } 倒计时(10);
霍夫施塔特定律也适用于软件项目。
The essence of human language is, according to Chomsky, the ability of finite brains to produce what he considers to be infinite grammars. By this he means not only that there is no upper limit on what we can say, but that there is no upper limit on the number of sentences our language has, there's no upper limit on the size of any particular sentence. Chomsky has claimed that the fundamental tool that underlies all of this creativity of human language is recursion: the ability for one phrase to reoccur inside another phrase of the same type. If I say "John's brother's house", I have a noun, "house", which occurs in a noun phrase, "brother's house", and that noun phrase occurs in another noun phrase, "John's brother's house". This makes a lot of sense, and it's an interesting property of human language.
参考文献
递归与人类思想
要理解递归,你只需要看看洗发水瓶上的标签:
function repeat()
{
rinse();
lather();
repeat();
}
这样做的问题是没有终止条件,递归将无限重复,或者直到洗发水或热水用完为止(外部终止条件,类似于吹你的堆栈)。
这与其说是一个问题,不如说是一个抱怨。关于递归你有更具体的问题吗?就像乘法一样,人们不会写很多关于它的东西。
说到乘法,想想这个。
问题:
* b是什么?
答:
如果b = 1,就是a。 否则就是a+a*(b-1)
* (b - 1)是什么?请参考上面的问题来解决这个问题。
构建递归函数的真正数学方法如下:
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.