16.4　递归函数

在说明什么是“递归函数”之前，让我们先讲一段小故事：1987年在陕西省宝鸡市的法门寺残塔中发现了一个神秘的盒子，现场考古人员打开后发现里面又是一个盒子，如此一共打开了8个盒子中的盒子，最终发现了一枚佛祖舍利（后证实是个假舍利）。如果把“打开盒子”这种行为当作是一次“函数调用”，这里就一共调用了8次，如果把整个过程从运行程序的角度来描述就是：调用“打开盒子”函数打开第一个盒子，如果发现里面还是盒子，则继续调用“打开盒子”函数打开第二只盒子，以此类推，直到不再有盒子为止——这种“类推”的方法用程序中的术语解释就是“递归”，具有“递归”功能的函数则被称为“递归函数”。递归函数的典型特征为：在函数体中继续调用函数自身。

那么这里就出现了一个问题，如果这种递归毫无止境地执行下去，是不是就成了“无限循环”了？答案是肯定的，所以递归函数一定要有结束递归的条件，当满足该条件时，递归就会终止。典型的递归函数的结构如下所示：

  1. function recursion() {
  2.       recursion
  3.       conditionThatEndTheRecursion      #
  4. 停止递归的条件
  5. }

数学中有个经典的需要使用递归算法计算的公式是：阶乘。这里只讨论正整数阶乘的情况，任何大于1的自然数n阶乘的计算公式为：n!=1×2×3×…×n，或写成n!=n×(n-1)!，终止条件为0!=1。按照该思路创建脚本factorial01.sh，内容如下：

  1. [root@localhost ~]# cat factorial01.sh 
  2. #!binbash
  3. function factorial01() {  
  4.        local NUMBER=$1
  5.        if [ $NUMBER -le 0 ]; then       #
  6. 这里是递归停止的条件
  7.                 RES=1  
  8.        else  
  9.                factorial01 $((NUMBER-1))  
  10.                TEMP=$RES 
  11.                NUMBER=$NUMBER
  12.                RES=$((NUMBER*TEMP))  
  13.        fi  
  14. }  
  15. factorial01 $1 
  16. echo $RES
  17. #
  18. 使用该脚本计算指定正整数的阶乘
  19. #
  20. 为了观察脚本运行过程，使用-x
  21. 参数跟踪脚本的运行细节
  22. [root@localhost ~]              # bash -x factorial01.sh 6
  23. + factorial01 6         #
  24. 当NUMBER
  25. 为6
  26. 时，由于6
  27. 不等于0
  28. ，进入嵌套
  29. + local NUMBER=6
  30. + '[' 6 -le 0 ']'
  31. + factorial01 5 #
  32. 第一次嵌套时，NUMBER
  33. 为5
  34. ，继续进入嵌套
  35. + local NUMBER=5
  36. + '[' 5 -le 0 ']'
  37. + factorial01 4 #
  38. 第二次嵌套时，NUMBER
  39. 为4
  40. ，继续进入嵌套
  41. + local NUMBER=4
  42. + '[' 4 -le 0 ']'
  43. + factorial01 3 #
  44. 第三次嵌套时，NUMBER
  45. 为3
  46. ，继续进入嵌套
  47. + local NUMBER=3
  48. + '[' 3 -le 0 ']'
  49. + factorial01 2 #
  50. 第四次嵌套时，NUMBER
  51. 为2
  52. ，继续进入嵌套
  53. + local NUMBER=2
  54. + '[' 2 -le 0 ']'
  55. + factorial01 1 #
  56. 第五次嵌套时，NUMBER
  57. 为1
  58. ，继续进入嵌套
  59. + local NUMBER=1
  60. + '[' 1 -le 0 ']'
  61. + factorial01 0 #
  62. 第六次嵌套时，NUMBER
  63. 为0
  64. ，当前RES=1
  65. + local NUMBER=0
  66. + '[' 0 -le 0 ']'
  67. + RES=1
  68. + TEMP=1
  69. + NUMBER=1
  70. + RES=1 #
  71. 第六次嵌套的计算结果为1
  72. ，返回给第五次嵌套
  73. + TEMP=1
  74. + NUMBER=2
  75. + RES=2 #
  76. 第五次嵌套的计算结果为2
  77. ，返回给第四次嵌套
  78. + TEMP=2
  79. + NUMBER=3
  80. + RES=6 #
  81. 第四次嵌套的计算结果为6
  82. ，返回给第三次嵌套
  83. + TEMP=6
  84. + NUMBER=4
  85. + RES=24        #
  86. 第三次嵌套的计算结果为24
  87. ，返回给第二次嵌套
  88. + TEMP=24
  89. + NUMBER=5
  90. + RES=120       #
  91. 第二次嵌套的计算结果为120
  92. ，返回给第一次嵌套
  93. + TEMP=120
  94. + NUMBER=6
  95. + RES=720       #
  96. 第一次嵌套的计算结果为720
  97. ，计算结束
  98. + echo 720
  99. 720

递归另一个典型的例子是“汉诺塔”游戏。该游戏源自印度一个古老的传说：在印度北部的贝拿勒斯神庙中，一块黄铜板上插着三根宝石针，其中一根从下到上穿了由大到小的64个金盘片，这就是所谓的汉诺塔。僧侣们不分白天黑夜地按照下面的法则移动这些金盘片，但必须满足以下两个条件：

1）一次只能移动一个盘片；

2）所有宝石针上的盘片只能是小的在大的上面。

僧侣们预言，当所有的金盘片都从最初所在的那根宝石针上移动到另一根上的时候，便是世界的尽头。

实际上这只是一个传说。但我们可以用科学的算法算出这个游戏的复杂度为f(64)=2^64-1，如果按照正确的方法移动盘片，并且可以做到每秒移动一次，那也要耗费5845亿年——届时可能真的是世界的尽头了。

为了简化汉诺塔游戏，这里只用4个盘片，如图16-1所示。我们的任务是将A柱上的4个盘片搬移到C柱上。将动作分解为以下几步：

第一步，将A柱上的3个盘片搬移到B柱上（递归搬移）；

第二步，将A柱上的一个盘片搬移到C柱上；

第三步，B柱上的3个盘片搬移到C柱上（递归搬移）。

16.4　递归函数 - 图1

图16-1　汉诺塔

使用Shell脚本实现如下：

  1. [root@localhost ~]# cat hanoi01.sh
  2. #! binbash
  3. function hanoi01()  
  4. {  
  5.     local num=$1  
  6.     if [ "$num" -eq "1" ];then  
  7.         echo "Move:$2----->$4"     
  8.     else  
  9.         hanoi01 $((num-1)) $2 $4 $3  
  10.         echo "Move:$2----->$4"  
  11.         hanoi01 $((num-1)) $3 $2 $4  
  12.     fi  
  13. }  
  14. hanoi01 4 A B C #
  15. 将4
  16. 个盘片从A
  17. 柱上通过B
  18. 、C
  19. 柱移动到C
  20. 柱上
  21. #
  22. 运行结果
  23. [root@localhost ~]# bash hanoi01.sh
  24. Move:A----->B
  25. Move:A----->C
  26. Move:B----->C
  27. Move:A----->B
  28. Move:C----->A
  29. Move:C----->B
  30. Move:A----->B
  31. Move:A----->C
  32. Move:B----->C
  33. Move:B----->A
  34. Move:C----->A
  35. Move:B----->C
  36. Move:A----->B
  37. Move:A----->C
  38. Move:B----->C

笔者想在结束本节之前谈谈个人对“递归函数”的看法：嵌套函数天生的结构就注定了其晦涩的可读性，在不少大公司内部的开发规范中也明确规定了不允许使用递归，所以在实际工作中要尽量避免使用递归。不过实际上你更可能根本没有使用递归的机会——从笔者多年从事Linux系统管理的经验来看，基本上不存在必须使用递归才能解决问题的场景。