Bash 中的递归函数【转载】

作为 Linux/Unix 系统上内核与用户之间的接口，shell 由于使用方便、可交互能力强、具有强大的编程能力等特性而受到广泛的应用。bash（Bourne Again shell）是对 Bourne shell 的扩展，并且综合了很多 csh 和 Korn Shell 中的优点，使得 bash 具有非常灵活且强大的编程接口，同时又有很友好的用户界面。bash 所提供的诸如命令补齐、通配符、命令历史记录、别名之类的新特性，使其迅速成为很多用户的首选。

注意： 【本文】转载至IBM developerworks社区，如有兴趣查看类似的其他文章，可以访问:IBM developerworks查阅。

然而，作为一种解释性语言，bash 在编程能力方面提供的支持并不像其他编译性的语言（例如 C 语言）那样完善，执行效率也会低很多，这些缺点在编写函数（尤其是递归函数）时都展现的一览无余。本文将从经典的 fork 炸弹入手，逐一介绍在 bash 中编写递归函数时需要注意问题，并探讨各种问题的解决方案。

尽管本文是以 bash 为例介绍相关概念，但是类似的思想基本上也适用于其他 shell。

递归经典：fork 炸弹

函数在程序设计中是一个非常重要的概念，它可以将程序划分成一个个功能相对独立的代码块，使代码的模块化更好，结构更加清晰，并可以有效地减少程序的代码量。递归函数更是充分提现了这些优点，通过在函数定义中调用自身，可以将复杂的计算问题变成一个简单的迭代算法，当回溯到边界条件时，再逐层返回上一层函数。有很多数学问题都非常适合于采用递归的思想来设计程序求解，例如阶乘、汉诺（hanoi）塔等。

可能很多人都曾经听说过 fork 炸弹，它实际上只是一个非常简单的递归程序，程序所做的事情只有一样：不断 fork 一个新进程。由于程序是递归的，如果没有任何限制，这会导致这个简单的程序迅速耗尽系统里面的所有资源。

在 bash 中设计这样一个 fork 炸弹非常简单，Jaromil 在 2002 年设计了最为精简的一个 fork炸弹的实现，整个程序从函数定义到调用仅仅包含 13 个字符，如清单 1 所示。

清单1. bash 中的 fork 炸弹

.(){ .|.& };.

这串字符乍看上去根本就看不出个所以然来，下面让我们逐一解释一下它究竟在干些什么。为了解释方便，我们对清单1中的内容重新设置一下格式，并在前面加上了行号，如清单 2 所示。

清单2. bash 中的 fork 炸弹的解释
1 .()
2 {
3  .|.&
4 }
5 ;
6 .
  • 第 1 行说明下面要定义一个函数，函数名为小数点，没有可选参数。
  • 第 2 行表示函数体开始。
  • 第 3 行是函数体真正要做的事情，首先它递归调用本函数，然后利用管道调用一个新进程（它要做的事情也是递归调用本函数），并将其放到后台执行。
  • 第 4 行表示函数体结束。
  • 第 5 行并不会执行什么操作，在命令行中用来分隔两个命令用。从总体来看，它表明这段程序包含两个部分，首先定义了一个函数，然后调用这个函数。
  • 第 6 行表示调用本函数。

对于函数名，大家可能会有所疑惑，小数点也能做函数名使用吗？毕竟小数点是 shell 的一个内嵌命令，用来在当前 shell 环境中读取指定文件，并运行其中的命令。实际上的确可以，这取决于 bash 对命令的解释顺序。默认情况下，bash 处于非 POSIX 模式，此时对命令的解释顺序如下：

  • 关键字，例如 if、for 等。
  • 别名。别名不能与关键字相同，但是可以为关键字定义别名，例如 end=fi。
  • 特殊内嵌命令，例如 break、continue 等。POSIX 定义的特殊内嵌命令包括：.（小数点）、:（冒号）、break、continue、eval、exec、exit、export、readonly、return、set、shift、times、trap 和 unset。bash 又增加了一个特殊的内嵌命令 source。
  • 函数。如果处于非 POSIX 模式，bash 会优先匹配函数，然后再匹配内嵌命令。
  • 非特殊内嵌命令，例如 cd、test 等。
  • 脚本和可执行程序。在 PATH 环境变量指定的目录中进行搜索，返回第一个匹配项。

由于默认情况下，bash 处于非 POSIX 模式，因此 fork 炸弹中的小数点会优先当成一个函数进行匹配。（实际上，Jaromil 最初的设计并没有使用小数点，而是使用的冒号，也能起到完全相同的效果。）要使用 POSIX 模式来运行 bash 脚本，可以使用以下三种方法：

  • 使用 --posix 选项启动 bash。
  • 在运行 bash 之后，执行 set -o posix 命令。
  • 使用 /bin/sh 。

最后一种方法比较有趣，尽管 sh 在大部分系统上是一个指向 bash 的符号链接，但是它所启用的却是 POSIX 模式，所有的行为都完全遵守 POSIX 规范。在清单 3 给出的例子中，我们可以发现，小数点在默认 bash 中被解释成一个函数，能够正常执行；但是在 sh 中，小数点却被当作一个内嵌命令，因此调用函数时会被认为存在语法错误，无法正常执行。

清单3. bash 与 sh 对命令匹配顺序的区别
[root@localhost ~]# ls -l /bin/bash /bin/sh
-rwxr-xr-x 1 root root 735144 2007-08-31 22:20 /bin/bash
lrwxrwxrwx 1 root root      4 2007-12-18 13:26 /bin/sh -> bash
[root@localhost ~]# echo $SHELL
/bin/bash
[root@localhost ~]# .() { echo hello; } ; .
hello
[root@localhost ~]# sh
sh-3.2# echo $SHELL
/bin/bash
sh-3.2# .() { echo hello; } ; .
sh: .': not a valid identifier
sh: .: filename argument required
.: usage: . filename [arguments]
sh-3.2#

一旦运行清单 1 给出的 fork 炸弹，会以2的指数次幂的速度不断产生新进程，这会导致系统资源会被迅速耗光，最终除非重新启动机器，否则基本上就毫无办法了。为了防止这会造成太大的损害，我们可以使用 ulimit 限制每个用户能够创建的进程数，如清单 4 所示。

清单4. 限制用户可以创建的进程数
[root@localhost ~]# ulimit -u 128
[root@localhost ~]# ulimit -a
core file size          (blocks, -c) 0
data seg size           (kbytes, -d) unlimited
max nice                        (-e) 20
file size               (blocks, -f) unlimited
pending signals                 (-i) unlimited
max locked memory       (kbytes, -l) unlimited
max memory size         (kbytes, -m) unlimited
open files                      (-n) 1024
pipe size            (512 bytes, -p) 8
POSIX message queues     (bytes, -q) unlimited
max rt priority                 (-r) unlimited
stack size              (kbytes, -s) 8192
cpu time               (seconds, -t) unlimited
max user processes              (-u) 128
virtual memory          (kbytes, -v) unlimited
file locks                      (-x) unlimited

[root@localhost ~]# .() { .|.& } ; .
[1] 6152

[root@localhost ~]# bash: fork: Resource temporarily unavailable
bash: fork: Resource temporarily unavailable
bash: fork: Resource temporarily unavailable
...

在清单 4 中，我们将用户可以创建的最大进程数限制为 128，执行 fork 炸弹会迅速 fork 出大量进程，此后会由于资源不足而无法继续执行。

fork 炸弹让我们认识到了递归函数的强大功能，同时也意识到一旦使用不当，递归函数所造成的破坏将是巨大的。实际上，fork 炸弹只是一个非常简单的递归函数，它并不涉及参数传递、返回值等问题，而这些问题在使用 bash 编程时是否有完善的支持呢？下面让我们通过几个例子来逐一介绍在 bash 中编写递归函数时应该注意的相关问题。

返回值问题

有一些经典的数学问题，使用递归函数来解决都非常方便。阶乘就是这样一个典型的问题，清单 5 给出了一个实现阶乘计算的 bash 脚本（当然，除了使用递归函数之外，简单地利用一个循环也可以实现计算阶乘的目的，不过本文以此为例来介绍递归函数的相关问题）。

清单5. 阶乘函数的 bash 实现
[root@localhost shell]# cat -n factorial1.sh
1  #!/bin/bash
2
3  factorial()
4  {
5    i=$1
6
7    if [ $i -eq 0 ]
8    then
9      return 1;
10    else
11      factorial expr $i - 1
12      return expr $i \* $? 
13    fi
14  }
15
16  if [ -z $1 ]
17  then
18    echo "Need one parameter."
19    exit 1
20  fi
21
22  factorial $1
23
24  echo $?
[root@localhost shell]# ./factorial1.sh 5
0

这个脚本看上去并没有什么问题：递归函数的参数传递和普通函数没什么不同，返回值是通过获取 $? 的值实现的，这是利用了执行命令的退出码。然而，最终的结果却显然是错误的。调试一下就会发现，当递归回溯到尽头时，变量 i 的值被修改为 0；而退出上次函数调用之后，变量 i 的新值也被带了回来，详细信息如清单 6 所示（请注意黑体部分）。

清单6. 调试 factorial1.sh 的问题
[root@localhost shell]# export PS4='+[$FUNCNAME: $LINENO] '
[root@localhost shell]# sh -x factorial1.sh 5
+[: 16] '[' -z 5 ']'
+[: 22] factorial 5
+[factorial: 5] i=5
+[factorial: 7] '[' 5 -eq 0 ']'
++[factorial: 11] expr 5 - 1
+[factorial: 11] factorial 4
+[factorial: 5] i=4
+[factorial: 7] '[' 4 -eq 0 ']'
++[factorial: 11] expr 4 - 1
+[factorial: 11] factorial 3
+[factorial: 5] i=3
+[factorial: 7] '[' 3 -eq 0 ']'
++[factorial: 11] expr 3 - 1
+[factorial: 11] factorial 2
+[factorial: 5] i=2
+[factorial: 7] '[' 2 -eq 0 ']'
++[factorial: 11] expr 2 - 1
+[factorial: 11] factorial 1
+[factorial: 5] i=1
+[factorial: 7] '[' 1 -eq 0 ']'
++[factorial: 11] expr 1 - 1
+[factorial: 11] factorial 0
+[factorial: 5] i=0
+[factorial: 7] '[' 0 -eq 0 ']'
+[factorial: 9] return 1
++[factorial: 12] expr 0 '*' 1
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
++[factorial: 12] expr 0 '*' 0
+[factorial: 12] return 0
+[: 24] echo 0
0

这段脚本问题的根源在于变量的作用域：在 shell 脚本中，不管是否在函数中定义，变量默认就是全局的，一旦定义之后，对于此后执行的命令全部可见。bash 也支持局部变量，不过需要使用 local 关键字进行显式地声明。local 是bash 中的一个内嵌命令，其作用是将变量的作用域设定为只有对本函数及其子进程可见。局部变量只能在变量声明的代码块中可见，这也就意味着在函数内声明的局部变量只能在函数代码块中才能被访问，它们并不会污染同名全局变量。因此为了解决上面这个程序的问题，我们应该使用 local 关键字将 i 声明为局部变量。修改后的脚本如清单 7 所示。

清单7. 递归函数中使用 local 关键字声明局部变量
[root@localhost shell]# cat -n factorial2.sh
1  #!/bin/bash
2
3  factorial()
4  {
5    local i=$1
6
7    if [ $i -eq 0 ]
8    then
9      return 1;
10    else
11      factorial expr $i - 1
12      return expr $i \* $? 
13    fi
14  }
15
16  if [ -z $1 ]
17  then
18    echo "Need one parameter."
19    exit 1
20  fi
21
22  factorial $1
23
24  echo $?
[root@localhost shell]# ./factorial2.sh 5
120
[root@localhost shell]# ./factorial2.sh 6208

这下 5 的阶乘计算对了，但是稍微大一点的数字都会出错，比如 6 的阶乘计算出来是错误的 208。这个问题的原因在于脚本中传递函数返回值的方式存在缺陷，$? 所能传递的最大值是 255，超过该值就没有办法利用这种方式来传递返回值了。解决这个问题的方法有两种，一种是利用全局变量，另外一种则是利用其他方式进行周转（例如标准输入输出设备）。清单 8 和清单 9 分别给出了这两种方法的参考实现。

清单8. 使用全局变量传递返回值
[root@localhost shell]# cat -n factorial3.sh
1  #!/bin/bash
2
3  factorial()
4  {
5    local i=$1
6
7    if [ $i -eq 0 ]
8    then
9      rtn=1
10    else
11      factorial expr $i - 1
12      rtn=expr $i \* $rtn 
13    fi
14
15    return $rtn
16  }
17
18  if [ -z $1 ]
19  then
20    echo "Need one parameter."
21    exit 1
22  fi
23
24  factorial $1
25
26  echo $rtn
[root@localhost shell]# ./factorial3.sh 6
720
清单9. 利用标准输入输出设备传递返回值
[root@localhost shell]# cat -n factorial4.sh
1  #!/bin/bash
2
3  factorial()
4  {
5    local i=$1
6
7    if [ $i -eq 0 ]
8    then
9      echo 1
10    else
11      local j=expr $i - 1
12      local k=factorial $j
13      echo expr $i \* $k 
14    fi
15  }
16
17  if [ -z $1 ]
18  then
19    echo "Need one parameter."
20    exit 1
21  fi
22
23  rtn=factorial $1
24  echo $rtn
[root@localhost shell]# ./factorial4.sh 6
720

尽管利用全局变量或标准输入输出设备都可以解决如何正确传递返回值的问题，但是它们却各有缺点：如果利用全局变量，由于全局变量对此后的程序全部可见，一旦被其他程序修改，就会出错，所以编写代码时需要格外小心，特别是在编写复杂的递归程序的时候；如果利用标准输入输出设备，那么递归函数中就存在诸多限制，例如任何地方都不能再向标准输出设备中打印内容，否则就可能被上一层调用当作正常输出结果读走了，另外速度方面也可能存在严重问题。

参数传递问题

在设计函数时，除了返回值之外，我们可能还希望所调用的函数还能够返回其他一些信息。例如，在上面的阶乘递归函数中，我们除了希望计算最后的结果之外，还希望了解这个函数一共被调用了多少次。熟悉 c 语言之类的读者都会清楚，这可以通过传递一个指针类型的参数实现。然而，在 bash 中并不支持指针，它提供了另外一种在解释性语言中常见的设计：间接变量引用（indirect variable reference）。让我们看一下下面这个例子：

var2=$var3
var1=$var2

其中变量 var2 的存在实际上就是为了让 var1 能够访问 var3，实际上也可以通过 var1 直接引用 var3 的值，方法是 var1=\$$var3（请注意转义字符是必须的，否则 $$ 符号会被解释为当前进程的进程 ID 号），这种方式就称为间接变量引用。从 bash2 开始，对间接变量引入了一种更为清晰的语法，方法是 var1=${!var3}。

清单 10 中给出了使用间接变量引用来统计阶乘函数被调用次数的实现。

清单10. 利用间接变量引用统计递归函数的调用次数
[root@localhost shell]# cat -n depth.sh
1  #!/bin/bash
2
3  factorial()
4  {
5    local i=$1
6    local l=$2
7
8    if [ $i -eq 0 ]
9    then
10      eval ${l}=1
11      rtn=1
12    else
13      factorial expr $i - 1 ${l}
14      rtn=expr $i \* $rtn 
15     
16      local k=${!l}
17      eval ${l}=expr ${k} + 1
18    fi
19
20    return $rtn
21  }
22
23  if [ -z $1 ]
24  then
25    echo "Need one parameter."
26    exit 1
27  fi
28
29  level=0
30  factorial $1 level
31
32  echo "The factorial of $1 is : $rtn"
33  echo " the function of factorial is invoked $level times."
[root@localhost shell]# ./depth.sh 6
The factorial of 6 is : 720
the function of factorial is invoked 7 times.

在上面我们曾经介绍过，为了解决变量作用域和函数返回值的问题，在递归函数中我们使用 local 声明局部变量，并采用全局变量来传递返回值。但是随着调用关系变得更加复杂，全局变量的值有可能在其他地方被错误地修改。实际上，使用局部变量也存在一个问题，下面让我们来看一下清单 11 中给出的例子。

清单11. 查找字符串在文件中是否存在，并计算所在行数和出现次数
[root@localhost shell]# cat -n getline1.sh
1  #!/bin/bash
2
3  GetLine()
4  {
5    string=$1
6    file=$2
7
8    line=grep -n $string $file
9    if [ $? -eq 0 ]
10    then
11      printf "$string is found as the %drd line in $file \n" echo $line \
| cut -f1 -d:
12      num=grep $string $file | wc -l
13      rtn=0
14    else
15      printf "$string is not found in $file \n"
16      num=0
17      rtn=1
18    fi
19
20    return $rtn;
21  }
22
23  if [ ! -f testfile.$$ ]
24  then
25    cat >> testfile.$$ <<EOF
26  first line .
27  second line ..
28  third line ...
29  EOF
30  fi
31
32  num=0
33  rtn=0
34  for i in "second" "six" "line"
35  do
36    echo
37    GetLine $i testfile.$$
38    echo "return value: $rtn"
39
40    if [ $num -gt 0 ]
41    then
42      echo "$num occurences found totally."
43    fi
44  done
[root@localhost shell]# ./getline1.sh
second is found as the 2rd line in testfile.4280
return value: 0
1 occurences found totally.
six is not found in testfile.4280
return value: 1
line is found as the 1rd line in testfile.4280
return value: 0
3 occurences found totally.
[root@localhost shell]#

这段程序的目的是查找某个字符串在指定文件中是否存在，如果存在，就计算第一次出现的行数和总共出现的次数。为了说明局部变量和后面提到的子函数的问题，我们故意将对出现次数的打印也放到了 GetLine 函数之外进行处理。清单 11 中全部使用全局变量，并没有出现什么问题。下面让我们来看一下将 GetLine 中使用的局部变量改用 local 声明后会出现什么问题，修改后的代码和执行结果如清单 12 所示。

清单12. 使用 local 声明局部变量需要注意的问题
[root@localhost shell]# cat -n getline2.sh
1  #!/bin/bash
2
3  GetLine()
4  {
5    local string=$1
6    local file=$2
7
8    local line=grep -n $string $file
9    if [ $? -eq 0 ]
10    then
11      printf "$string is found as the %drd line in $file \n" echo $line \
| cut -f1 -d:
12      num=grep $string $file | wc -l
13      rtn=0
14    else
15      printf "$string is not found in $file \n"
16      num=0
17      rtn=1
18    fi
19
20    return $rtn;
21  }
22
23  if [ ! -f testfile.$$ ]
24  then
25    cat >> testfile.$$ <<EOF
26  first line .
27  second line ..
28  third line ...
29  EOF
30  fi
31
32  num=0
33  rtn=0
34  for i in "second" "six" "line"
35  do
36    echo
37    GetLine $i testfile.$$
38    echo "return value: $rtn"
39
40    if [ $num -gt 0 ]
41    then
42      echo "$num occurences found totally."
43    fi
44  done
[root@localhost shell]# ./getline2.sh
second is found as the 2rd line in testfile.4300
return value: 0
1 occurences found totally.
six is found as the 0rd line in testfile.4300 return value: 0
line is found as the 1rd line in testfile.4300
return value: 0
3 occurences found totally.

清单 12 的运行结果显示，在文件中搜索 six 关键字时的结果是错误的，调试会发现，问题的原因在于：第 8 行使用 local 将 line 声明为局部变量，并将 grep 命令的执行结果赋值给 line 变量。然而不论 grep 是否成功在文件中找到匹配项（grep 程序找到匹配项返回值为 0，否则返回值为 1），第 9 行中 ? 的值总是 0。实际上，第 8 行相当于执行了两条语句：第一条语句使用 grep 在文件中查找匹配项，第二条语句将 grep 命令的结果赋值给变量 line，并设定其作用域只对于本函数及其子进程可见。因此第 9 行命令中? 的值实际上是执行 local 命令的返回值，不管 grep 命令的结果如何，它总是 0。

要解决这个问题，可以将第 8 行的命令拆分开，首先使用单独一行将变量 line 声明为 local的，然后再执行这条 grep 命令，并将结果赋值给变量 line（此时前面不能加上 local）。

解决变量作用域的另外一种方法是使用子 shell。所谓子 shell 是在当前 shell 环境中启动一个子 shell 来执行所调用的命令或函数，这个函数中所声明的所有变量都是局部变量，它们不会污染原有 shell 的名字空间。清单 13 给出了使用子 shell 修改后的例子。

清单13. 利用子 shell 实现局部变量
[root@localhost shell]# cat -n getline3.sh
1  #!/bin/bash
2
3  GetLine()
4  {
5    string=$1
6    file=$2
7
8    line=grep -n $string $file
9    if [ $? -eq 0 ]
10    then
11      printf "$string is found as the %drd line in $file \n" echo $line  \
| cut -f1 -d:
12      num=grep $string $file | wc -l
13      rtn=0
14    else
15      printf "$string is not found in $file \n"
16      num=0
17      rtn=1
18    fi
19
20    return $rtn;
21  }
22
23  if [ ! -f testfile.$$ ]
24  then
25    cat >> testfile.$$ <<EOF
26  first line .
27  second line ..
28  third line ...
29  EOF
30  fi
31
32  num=0
33  rtn=0
34  for i in "second" "six" "line"
35  do
36    echo
37    (GetLine $i testfile.$$)
38    echo "return value: $? (rtn = $rtn)"
39
40    if [ $num -gt 0 ]
41    then
42      echo "$num occurences found totally."
43    fi
44  done
[root@localhost shell]# ./getline3.sh
second is found as the 2rd line in testfile.4534
return value: 0 (rtn = 0)
six is not found in testfile.4534
return value: 1 (rtn = 0)
line is found as the 1rd line in testfile.4534
return value: 0 (rtn = 0)

在清单 13 中，GetLine 函数并不需要任何变化，变量定义和程序调用都沿用正常方式。唯一的区别在于调用该函数时，要将其作为一个子 shell 来调用（请注意第 37 行两边的圆括号）。另外一个问题是在子 shell 中修改的所有变量对于原有 shell 来说都是不可见的，这也就是为什么在第 38 行要通过 $? 来检查返回值，而 rtn 变量的值却是错误的。另外由于 num 在 GetLine 函数中也被当作是局部变量，同样无法将修改后的值传出来，因此也并没有打印所匹配到的 line 的数目是 3 行的信息。

解决上面这个问题就只能使用前面提到的利用标准输入输出设备的方法了，否则即使使用间接变量引用也无法正常工作。清单 14 给出了一个使用间接变量引用的例子，尽管我们使用不同的名字来命名全局变量和局部变量，从而确保不会引起同名混淆，但是依然无法正常工作。原因同样在于 GetLine 函数是在另外一个子进程中运行的，它对变量所做的更新随着子 shell 的退出就消失了。

清单14. 利用间接变量索引也无法解决子 shell 通过变量回传值的问题
[root@localhost shell]# cat -n getline4.sh
1  #!/bin/bash
2
3  GetLine()
4  {
5    string=$1
6    file=$2
7    num=$3
8    rtn=$4
9
10    line=grep -n $string $file
11    if [ $? -eq 0 ]
12    then
13      printf "$string is found as the %drd line in $file \n"  \
        echo $line | cut -f1 -d:
14      eval ${num}=grep $string $file | wc -l
15      eval ${rtn}=0
16    else
17      printf "$string is not found in $file \n"
18      eval ${num}=0
19      eval ${rtn}=1
20    fi
21
22    return ${!rtn};
23  }
24
25  if [ ! -f testfile.$$ ]
26  then
27    cat >> testfile.$$ <<EOF
28  first line .
29  second line ..
30  third line ...
31  EOF
32  fi
33
34  g_num=0
35  g_rtn=0
36  for i in "second" "six" "line"
37  do
38    echo
39    (GetLine $i testfile.$$ g_num g_rtn)
40    echo "return value: $? (g_rtn = $g_rtn)"
41
42    if [ $g_num -gt 0 ]
43    then
44      echo "$g_num occurence(s) found totally."
45    fi
46  done
[root@localhost shell]# ./getline4.sh
second is found as the 2rd line in testfile.4576
return value: 0 (g_rtn = 0)
six is not found in testfile.4576
return value: 1 (g_rtn = 0)
line is found as the 1rd line in testfile.4576
return value: 0 (g_rtn = 0)

性能问题

尽管编写 bash 脚本可以实现递归函数，但是由于先天性的不足，使用 bash 脚本编写的递归函数的性能都比较差，问题的根本在于它的主要流程都是要不断地调用其他程序，这会 fork 出很多进程，从而极大地增加运行时的开销。下面让我们来看一个计算累加和的例子，清单 15 和清单 16 给出了两个实现，它们分别利用全局变量和标准输入输出设备来传递返回值。为了简单起见，我们也不对输入参数进行任何判断。

清单15. 累加和，利用全局变量传递返回值
[root@localhost shell]# cat -n sum1.sh
1  #!/bin/bash
2
3  sum()
4  {
5    local i=$1
6
7    if [ $i -eq 1 ]
8    then
9      rtn=1
10    else
11      sum expr $i - 1
12      rtn=expr $i + $rtn 
13    fi
14
15    return $rtn
16  }
17
18  if [ -z $1 ]
19  then
20    echo "Need one parameter."
21    exit 1
22  fi
23
24  sum $1
25
26  echo $rtn
清单16. 累加和，利用标准输入输出设备传递返回值
[root@localhost shell]# cat -n sum2.sh
1  #!/bin/bash
2
3  sum()
4  {
5    local i=$1
6
7    if [ $i -eq 1 ]
8    then
9      echo 1
10    else
11      local j=expr $i - 1
12      local k=sum $j
13      echo expr $i + $k 
14    fi
15  }
16
17  if [ -z $1 ]
18  then
19    echo "Need one parameter."
20    exit 1
21  fi
22
23  rtn=sum $1
24  echo $rtn

下面让我们来测试一下这两个实现的性能会有多大的差距：

清单17. 利用全局变量和标准输入输出设备传递返回值的性能比较
[root@localhost shell]# cat -n run.sh
1  #!/bin/bash
2
3  if [ $# -lt 2 ]
4  then
5    echo "Usage: $0 [number] [executable list]"
6    exit 1
7  fi
8
9  NUM=$1
10  shift
11
12  for i in $*
13  do
14    echo "Running command: $i $NUM"
15    time ./$i $NUM
16
17    sleep 5
18    echo
19  done
[root@localhost shell]# ./run.sh 500 sum1.sh sum2.sh
Running command: sum1.sh 500
125250
real    0m8.336s
user    0m0.532s
sys     0m7.772s
Running command: sum2.sh 500
125250
real    0m20.775s
user    0m1.316s
sys     0m17.741s

在计算 1 到 500 的累加和时，利用标准输入输出设备传递返回值的方法速度要比利用全局变量慢 1 倍以上。随着迭代次数的增加，二者的差距也会越来越大，主要原因标准输入输出设备都是字符设备，从中读写数据耗时会很长；而全局变量则是在内存中进行操作的，速度会明显快很多。

为了提高 shell 脚本的性能，在编写 shell 脚本时，应该尽量多使用 shell 的内嵌命令，而不能过多地调用外部脚本或命令，因为调用内嵌命令时不会 fork 新的进程，而是在当前 shell 环境中直接执行这些命令，这样可以减少很多系统开销。以计算表达式的值为例，前面的例子我们都是通过调用 expr 来对表达式进行求值的，但是 bash 中提供了一些内嵌的计算表达式手段，例如 ((i = j +k)) 与 i=expr $j + $k 的效果就是完全相同的，都是计算变量 j 与 k 的值，并将结果赋值给变量 i，但是前者却节省了一次 fork 新进程以及执行 expr 命令的开销。下面让我们对清单 15 中的脚本进行一下优化，如清单 18 所示。

清单18. 优化后的计算累加和的脚本
[root@localhost shell]# cat -n sum3.sh
1  #!/bin/bash
2
3  sum()
4  {
5    local i=$1
6
7    if [ $i -eq 1 ]
8    then
9      rtn=1
10    else
11      sum $(($i - 1))
12      ((rtn = rtn + i))
13    fi
14
15    return $rtn
16  }
17
18  sum $1
19
20  echo $rtn

现在让我们来比较一下优化前后的性能差距，如清单 19 所示。

清单19. 优化前后的性能对比
[root@localhost shell]# ./run.sh 2000 sum1.sh sum3.sh
Running command: sum1.sh 2000
2001000
real    1m19.378s
user    0m15.877s
sys     1m3.472s
Running command: sum3.sh 2000
2001000
real    0m12.202s
user    0m10.949s
sys     0m1.220s

可以看出，在迭代 2000 次时，优化后的脚本速度要比优化前快 5 倍以上。但是无论如何，使用 shell 脚本编写的递归函数的执行效率都不高，c 语言的实现与其相比，快了可能都不止一个数量级，详细数据请参看清单 20。

清单20. c 语言与 bash 脚本实现递归函数的对比
[root@localhost shell]# cat -n sum.c
1  #include <stdlib.h>
2  #include <stdio.h>
3
4  int sum(int i)
5  {
6    if (i == 1)
7      return 1;
8    else
9      return i + sum(i-1);
10  }
11
12  int main(int argc, char **argv[])
13  {
14    printf("%d\n", sum(atoi((char *)argv[1])));
15  }
[root@localhost shell]# gcc -O2 -o sum sum.c
[root@localhost shell]# ./run.sh 3000 sum sum3.sh
Running command: sum 3000
4501500
real    0m0.004s
user    0m0.000s
sys     0m0.004s
Running command: sum3.sh 3000
4501500
real    0m31.182s
user    0m28.998s
sys     0m2.004s

因此，如果编写对性能要求很高的递归程序，还是选择其他语言实现好了，这并不是 shell 的强项。

小结

本文从经典的 fork 炸弹递归函数入手，逐一介绍了在 bash 中编写递归函数时需要注意的问题，包括返回值、参数传递和性能等方面的问题以及解决方法，并对如何提高 shell 脚本性能提供了一个建议。

下载

相关主题

  • 请访问 bash 的主页，从这里可以获得最新版本的 bash 源代码以及详细的手册。
  • Shell 脚本调试技术一文中介绍了常用的一些 shell 脚本调试方法。
  • 希望拥有一个像 gdb 一样功能强大的 shell 脚本调试器吗？bashdb 就是最好的选择，详细信息请参看bashdb 的主页。
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 201,924评论 5赞 474
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,781评论 2赞 378
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 148,813评论 0赞 335
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,264评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,273评论 5赞 363
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,383评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,800评论 3赞 393
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,482评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,673评论 1赞 295
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,497评论 2赞 318
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,545评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,240评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,802评论 3赞 304
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,866评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,101评论 1赞 258
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,673评论 2赞 348
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,245评论 2赞 341

推荐阅读更多精彩内容

  • bash
    官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,357评论 0赞 5
  • 极迅云课（服务端教案）
    一、Python简介和环境搭建以及pip的安装 4课时实验课主要内容 【Python简介】： Python 是一个...
    _小老虎_阅读 5,713评论 0赞 10
  • shell
    第 2 章 SHELL 基础知识2.1 shell脚本我们在上面简单介绍了一下什么是shell脚本，现在我们来进一...
    LiWei_9e4b阅读 1,549评论 0赞 0
  • 【shell笔记>脚本】创建和使用shell函数
    来源： Linux命令行与shell脚本编程大全 博客地址，推荐电脑点 内容 基本的脚本函数返回值在函数中使用变量...
    王诗翔阅读 2,436评论 0赞 3
  • 心怀梦想
    心中有了梦想，看到的天空都是暖暖的蓝色
    Heaxui阅读 73评论 0赞 0