Skip to content
SRE运维进阶之路SRE运维进阶之路
devops
github icon
    • 第四部分 命令
        • 19 嵌入文档
          • 第二十一章 子shell
            • 第二十二章. 限制模式的Shell
              • 第二十三章. 进程替换
                  • 24.1 复杂函数和函数复杂性
                    • 24.2 局部变量
                      • 24.3 不使用局部变量的递归
                        • 斐波那契序列
                      • 25. 别名
                        • 26. 列表结构
                          • 27 数组
                            • 30 网络编程
                              • 33 选项
                                • 第34章 陷阱
                                  • 第36章 杂项
                                    • echo命令
                                    • 第六部分 Google Shell 风格指南
                                    • 前端学习笔记

                                      24.3 不使用局部变量的递归

                                      author iconLinuxStorycalendar icon2023年4月19日category icon
                                      • Linux
                                      tag icon
                                      • Bash
                                      timer icon大约 3 分钟

                                      此页内容
                                      • 斐波那契序列

                                      # 24.3 不使用局部变量的递归

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

                                      # 斐波那契序列

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

                                      例子 24-17. 汉诺塔

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