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

我整晚都在尝试着解决《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

我希望这对你有所帮助