24.3 不使用局部变量的递归

即使不适用局部变量，函数也可以递归的调用自身。

例子24-16. 斐波那契序列

  1. #!/bin/bash
  2. # fibo.sh : 斐波那契序列 (递归)
  3. # 作者: M. Cooper
  4. # License: GPL3
  6. # ----------算法--------------
  7. # Fibo(0) = 0
  8. # Fibo(1) = 1
  9. # else
  10. #   Fibo(j) = Fibo(j-1) + Fibo(j-2)
  11. # ---------------------------------
  13. MAXTERM=15       # 要产生的计算次数。
  14. MINIDX=2         # 如果下标小于2，那么 Fibo(idx) = idx.
  16. Fibonacci ()
  17. {
  18.     idx=$1   # 不需要是局部变量，为什么？
  19.     if [ "$idx" -lt "$MINIDX" ]
  20.     then
  21.         echo "$idx"  # 前两个下标是0和1 ... 从上面的算法可以看出来。
  22.     else
  23.         (( --idx ))  # j-1
  24.         term1=$( Fibonacci $idx )   #  Fibo(j-1)
  25.         (( --idx ))  # j-2
  26.         term2=$( Fibonacci $idx )   #  Fibo(j-2)
  27.         echo $(( term1 + term2 ))
  28.     fi
  29.     #  一个丑陋的实现
  30.     #  C语言里，一个更加优雅的斐波那契递归实现
  31.     #+ 是一个简单的只需要7-10代码的算法翻译。
  32. }
  34. for i in $(seq 0 $MAXTERM)
  35. do  # 计算 $MAXTERM+1 次.
  36.     FIBO=$(Fibonacci $i)
  37.     echo -n "$FIBO "
  38. done
  39. # 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610
  40. # 要花费一段时间，不是么？ 一个递归脚本是有些慢的。
  42. echo
  44. exit 0

例子 24-17. 汉诺塔

  1. #! /bin/bash
  2. #
  3. # 汉诺塔
  4. # Bash script
  5. # Copyright (C) 2000 Amit Singh. All Rights Reserved.
  6. # http://hanoi.kernelthread.com
  7. #
  8. # 在 Bash version 2.05b.0(13)-release下通过测试.
  9. # 同样在Bash3.x版本下工作正常。
  10. #
  11. #  在 "Advanced Bash Scripting Guide" 一书中使用
  12. #+ 经过了脚本作者的许可。
  13. #  ABS的作者对脚本进行了轻微的修改和注释。
  14. #=================================================================#
  15. #  汉诺塔是由Edouard Lucas,提出的数学谜题， 
  16. #+  他是19世纪的法国数学家。
  17. #
  18. # 有三个直立的柱子竖在地面上。
  19. # 第一个柱子上有一组盘子套在上面。
  20. # 这些盘子是平的，中间有孔，
  21. #+ 可以套在柱子上面。
  22. # 这些盘子的直径不同，它们从下而上， 
  23. #+ 按照尺寸递减的顺序摆放。
  24. # 也就是说，最小的在最上边，最大的在最下面。
  25. #
  26. # 现在的任务是要把这组盘子  
  27. #+ 从一个柱子上全部搬到另一个柱子上 
  28. # 你每次只能将一个盘子从一个柱子移到另一个柱子上。
  29. # 你也可以把盘子从其他的柱子上移回到原来的柱子上。
  30. # 你只能把小的盘子放到大的盘子上。
  31. #+ 反过来就不行。
  32. # 切记，绝对不能把大盘子放到小盘子的上面。
  33. # 如果盘子的数量比较少，那么移不了几次就能完成。
  34. #+ 但是随着盘子数量的增加，
  35. #+ 移动次数几乎成倍的增长，
  36. #+ 而且移动的“策略”也会变得越来越复杂。
  37. #
  38. # 想了解更多信息的话，请访问http://hanoi.kernelthread.com
  39. #+ 或者 pp. 186-92 of _The Armchair Universe_ by A.K. Dewdney.
  40. #
  41. #
  42. #           ...             ...         ...
  43. #           | |             | |         | |
  44. #          _|_|_            | |         | |
  45. #         |_____|           | |         | |
  46. #        |_______|          | |         | |
  47. #       |_________|         | |         | |
  48. #      |___________|        | |         | |
  49. #     |             |       | |         | |
  50. # .--------------------------------------------------------------. 
  51. # |**************************************************************| 
  52. #            #1              #2          #3
  53. # #=================================================================#
  55. E_NOPARAM=66  # 没有参数传给脚本。
  56. E_BADPARAM=67 # 传给脚本的盘子个数不符合要求。
  57. Moves=        # 保存移动次数的全局变量。
  58.               # 这里修改了原来的脚本。
  60. dohanoi() {   # 递归函数
  61.     case $1 in
  62.     0)
  63.         ;;
  64.     *)
  65.         dohanoi "$(($1-1))" $2 $4 $3
  66.         echo move $2 "-->" $3
  67.         ((Moves++))          # 这里修改了原来的脚本。
  68.         dohanoi "$(($1-1))" $4 $3 $2
  69.         ;;
  70.     esac 
  71. }
  73. case $# in
  74.     1) case $(($1>0)) in     # 至少要有一个盘子
  75.         1)  # Nested case statement.
  76.             dohanoi $1 1 3 2
  77.             echo "Total moves = $Moves"     # 2^n - 1, where n = # of disks.
  78.             exit 0;
  79.             ;; 
  80.         *)    
  81.             echo "$0: illegal value for number of disks";
  82.             exit $E_BADPARAM;
  83.             ;;
  84.         esac ;;
  85.     *)
  86.         echo "usage: $0 N"
  87.         echo "       Where \"N\" is the number of disks."
  88.         exit $E_NOPARAM;
  89.         ;;
  90.     esac
  92. # 练习:
  93. # ---------
  94. # 1) 这个位置以下的代码会不会执行？ 
  95. #    为什么不(容易)
  96. # 2) 解释一下这个 "dohanoi" 函数的运行原理.
  97. #    (比较难 可以参考上面的Dewdney 的引用)