Php文档 Php问答行业资讯 Php论坛 Php手册 Php博客

游戏榜单

软件榜单

关闭导航

热搜榜

热门下载

热门标签

关闭搜索

php爱好者> php文档>Bash中的递归函数

Bash中的递归函数

时间：2008-03-21 来源：剑心通明

级别：初级

冯锐([email protected]), 软件工程师, IBM
丁成([email protected]), 软件工程师, IBM

2008 年 2 月 21 日

作为一种解释性语言，尽管 bash 对编程提供了一定的支持，但是在某些方面却存在一些限制。本文将逐一探讨在 bash 中编写递归函数时需要注意的返回值、参数传递和性能等方面的问题，并给出可能的解决方法，最后对如何优化 shell 脚本性能提供了一个建议。

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

然而，作为一种解释性语言，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 {
5locali=$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 6
208

这下 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 {
5local string=$1
6local file=$2
7
8local 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
7num=$3
8rtn=$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:`
14eval ${num}=`grep $string $file | wc -l`
15eval ${rtn}=0
16 else
17 printf "$string is not found in $file \n"
18eval ${num}=0
19eval ${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
34g_num=0
35g_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