我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
我在学校里很难理解递归。每当教授谈到它的时候,我似乎都懂了,但当我自己尝试的时候,它完全震撼了我的大脑。
我整晚都在尝试着解决《Towers of Hanoi》这款游戏,结果完全出乎我的意料。我的课本只有大约30页关于递归的内容,所以它不是很有用。有人知道哪些书籍或资源可以帮助澄清这个话题吗?
当前回答
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.
其他回答
这与其说是一个问题,不如说是一个抱怨。关于递归你有更具体的问题吗?就像乘法一样,人们不会写很多关于它的东西。
说到乘法,想想这个。
问题:
* b是什么?
答:
如果b = 1,就是a。 否则就是a+a*(b-1)
* (b - 1)是什么?请参考上面的问题来解决这个问题。
我认为这个非常简单的方法可以帮助你理解递归。该方法将调用自身,直到某个条件为真,然后返回:
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 butt将不会调用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
如你所见,递归方法要好得多。
实际上,使用递归是为了降低手头问题的复杂性。你应用递归,直到你达到一个简单的基本情况,可以很容易地解决。这样就可以解决最后一个递归步骤。用这些递归步骤就可以解决最初的问题。
你在用哪本书?
关于算法的标准教科书是Cormen & Rivest。我的经验是,它很好地教授了递归。
递归是编程中较难掌握的部分之一,虽然它确实需要本能,但它是可以学习的。但它确实需要一个好的描述,好的例子和好的插图。
此外,30页通常是很多的,30页是用一种编程语言编写的。在你从一本普通的书中理解递归之前,不要尝试用C或Java学习递归。
我会用一个例子来解释。
你知道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
我希望这对你有所帮助