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

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


当前回答

要向一个六岁的孩子解释递归,首先要向一个五岁的孩子解释,然后再等一年。

实际上,这是一个有用的反例,因为递归调用应该更简单,而不是更难。向一个5岁的孩子解释递归就更难了,尽管你可以在0点停止递归,但你没有简单的解决方案来向一个0岁的孩子解释递归。

要使用递归解决一个问题,首先将其细分为一个或多个可以用相同方法解决的更简单的问题,然后当问题简单到无需进一步递归就可以解决时,您可以返回到更高的级别。

事实上,这是用递归方法来解决问题的递归定义。

其他回答

我会用一个例子来解释。

你知道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

我希望这对你有所帮助

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

Common Lisp中的简单递归示例:

MYMAP对列表中的每个元素应用一个函数。

1)空列表没有元素,所以我们返回空列表-()和NIL都是空列表。

2)将函数应用到第一个列表,对列表的其余部分调用MYMAP(递归调用),并将两个结果合并到一个新列表中。

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

让我们观察跟踪执行。在输入函数时,输出参数。在退出函数时,输出结果。对于每个递归调用,输出将按级别缩进。

这个例子对列表(1 2 3 4)中的每个数字调用SIN函数。

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

这是我们的结果:

(0.841471 0.9092975 0.14112002 -0.75680256)

我认为这个非常简单的方法可以帮助你理解递归。该方法将调用自身,直到某个条件为真,然后返回:

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

如你所见,递归方法要好得多。

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

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

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

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

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

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