作為 Linux/Unix 系統(tǒng)上內(nèi)核與用戶之間的接口，shell 由于使用方便、可交互能力強(qiáng)、具有強(qiáng)大的編程能力等特性而受到廣泛的應(yīng)用。bash（Bourne Again shell）是對 Bourne shell 的擴(kuò)展，并且綜合了很多 csh 和 Korn Shell 中的優(yōu)點(diǎn)，使得 bash 具有非常靈活且強(qiáng)大的編程接口，同時又有很友好的用戶界面。bash 所提供的諸如命令補(bǔ)齊、通配符、命令歷史記錄、別名之類的新特性，使其迅速成為很多用戶的首選。

注意： 【本文】轉(zhuǎn)載至IBM developerworks社區(qū)，如有興趣查看類似的其他文章，可以訪問:IBM developerworks查閱。

然而，作為一種解釋性語言，bash 在編程能力方面提供的支持并不像其他編譯性的語言（例如 C 語言）那樣完善，執(zhí)行效率也會低很多，這些缺點(diǎn)在編寫函數(shù)（尤其是遞歸函數(shù)）時都展現(xiàn)的一覽無余。本文將從經(jīng)典的 fork 炸彈入手，逐一介紹在 bash 中編寫遞歸函數(shù)時需要注意問題，并探討各種問題的解決方案。

盡管本文是以 bash 為例介紹相關(guān)概念，但是類似的思想基本上也適用于其他 shell。

遞歸經(jīng)典：fork 炸彈

函數(shù)在程序設(shè)計(jì)中是一個非常重要的概念，它可以將程序劃分成一個個功能相對獨(dú)立的代碼塊，使代碼的模塊化更好，結(jié)構(gòu)更加清晰，并可以有效地減少程序的代碼量。遞歸函數(shù)更是充分提現(xiàn)了這些優(yōu)點(diǎn)，通過在函數(shù)定義中調(diào)用自身，可以將復(fù)雜的計(jì)算問題變成一個簡單的迭代算法，當(dāng)回溯到邊界條件時，再逐層返回上一層函數(shù)。有很多數(shù)學(xué)問題都非常適合于采用遞歸的思想來設(shè)計(jì)程序求解，例如階乘、漢諾（hanoi）塔等。

可能很多人都曾經(jīng)聽說過 fork 炸彈，它實(shí)際上只是一個非常簡單的遞歸程序，程序所做的事情只有一樣：不斷 fork 一個新進(jìn)程。由于程序是遞歸的，如果沒有任何限制，這會導(dǎo)致這個簡單的程序迅速耗盡系統(tǒng)里面的所有資源。

在 bash 中設(shè)計(jì)這樣一個 fork 炸彈非常簡單，Jaromil 在 2002 年設(shè)計(jì)了最為精簡的一個 fork炸彈的實(shí)現(xiàn)，整個程序從函數(shù)定義到調(diào)用僅僅包含 13 個字符，如清單 1 所示。

清單1. bash 中的 fork 炸彈

.(){ .|.& };.

這串字符乍看上去根本就看不出個所以然來，下面讓我們逐一解釋一下它究竟在干些什么。為了解釋方便，我們對清單1中的內(nèi)容重新設(shè)置一下格式，并在前面加上了行號，如清單 2 所示。

清單2. bash 中的 fork 炸彈的解釋

1 .()
2 {
3  .|.&
4 }
5 ;
6 .

• 第 1 行說明下面要定義一個函數(shù)，函數(shù)名為小數(shù)點(diǎn)，沒有可選參數(shù)。
• 第 2 行表示函數(shù)體開始。
• 第 3 行是函數(shù)體真正要做的事情，首先它遞歸調(diào)用本函數(shù)，然后利用管道調(diào)用一個新進(jìn)程（它要做的事情也是遞歸調(diào)用本函數(shù)），并將其放到后臺執(zhí)行。
• 第 4 行表示函數(shù)體結(jié)束。
• 第 5 行并不會執(zhí)行什么操作，在命令行中用來分隔兩個命令用。從總體來看，它表明這段程序包含兩個部分，首先定義了一個函數(shù)，然后調(diào)用這個函數(shù)。
• 第 6 行表示調(diào)用本函數(shù)。

對于函數(shù)名，大家可能會有所疑惑，小數(shù)點(diǎn)也能做函數(shù)名使用嗎？畢竟小數(shù)點(diǎn)是 shell 的一個內(nèi)嵌命令，用來在當(dāng)前 shell 環(huán)境中讀取指定文件，并運(yùn)行其中的命令。實(shí)際上的確可以，這取決于 bash 對命令的解釋順序。默認(rèn)情況下，bash 處于非 POSIX 模式，此時對命令的解釋順序如下：

• 關(guān)鍵字，例如 if、for 等。
• 別名。別名不能與關(guān)鍵字相同，但是可以為關(guān)鍵字定義別名，例如 end=fi。
• 特殊內(nèi)嵌命令，例如 break、continue 等。POSIX 定義的特殊內(nèi)嵌命令包括：.（小數(shù)點(diǎn)）、:（冒號）、break、continue、eval、exec、exit、export、readonly、return、set、shift、times、trap 和 unset。bash 又增加了一個特殊的內(nèi)嵌命令 source。
• 函數(shù)。如果處于非 POSIX 模式，bash 會優(yōu)先匹配函數(shù)，然后再匹配內(nèi)嵌命令。
• 非特殊內(nèi)嵌命令，例如 cd、test 等。
• 腳本和可執(zhí)行程序。在 PATH 環(huán)境變量指定的目錄中進(jìn)行搜索，返回第一個匹配項(xiàng)。

由于默認(rèn)情況下，bash 處于非 POSIX 模式，因此 fork 炸彈中的小數(shù)點(diǎn)會優(yōu)先當(dāng)成一個函數(shù)進(jìn)行匹配。（實(shí)際上，Jaromil 最初的設(shè)計(jì)并沒有使用小數(shù)點(diǎn)，而是使用的冒號，也能起到完全相同的效果。）要使用 POSIX 模式來運(yùn)行 bash 腳本，可以使用以下三種方法：

• 使用 --posix 選項(xiàng)啟動 bash。
• 在運(yùn)行 bash 之后，執(zhí)行 set -o posix 命令。
• 使用 /bin/sh 。

最后一種方法比較有趣，盡管 sh 在大部分系統(tǒng)上是一個指向 bash 的符號鏈接，但是它所啟用的卻是 POSIX 模式，所有的行為都完全遵守 POSIX 規(guī)范。在清單 3 給出的例子中，我們可以發(fā)現(xiàn)，小數(shù)點(diǎn)在默認(rèn) bash 中被解釋成一個函數(shù)，能夠正常執(zhí)行；但是在 sh 中，小數(shù)點(diǎn)卻被當(dāng)作一個內(nèi)嵌命令，因此調(diào)用函數(shù)時會被認(rèn)為存在語法錯誤，無法正常執(zhí)行。

清單3. bash 與 sh 對命令匹配順序的區(qū)別

[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#

一旦運(yùn)行清單 1 給出的 fork 炸彈，會以2的指數(shù)次冪的速度不斷產(chǎn)生新進(jìn)程，這會導(dǎo)致系統(tǒng)資源會被迅速耗光，最終除非重新啟動機(jī)器，否則基本上就毫無辦法了。為了防止這會造成太大的損害，我們可以使用 ulimit 限制每個用戶能夠創(chuàng)建的進(jìn)程數(shù)，如清單 4 所示。

清單4. 限制用戶可以創(chuàng)建的進(jìn)程數(shù)

[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 中，我們將用戶可以創(chuàng)建的最大進(jìn)程數(shù)限制為 128，執(zhí)行 fork 炸彈會迅速 fork 出大量進(jìn)程，此后會由于資源不足而無法繼續(xù)執(zhí)行。

fork 炸彈讓我們認(rèn)識到了遞歸函數(shù)的強(qiáng)大功能，同時也意識到一旦使用不當(dāng)，遞歸函數(shù)所造成的破壞將是巨大的。實(shí)際上，fork 炸彈只是一個非常簡單的遞歸函數(shù)，它并不涉及參數(shù)傳遞、返回值等問題，而這些問題在使用 bash 編程時是否有完善的支持呢？下面讓我們通過幾個例子來逐一介紹在 bash 中編寫遞歸函數(shù)時應(yīng)該注意的相關(guān)問題。

返回值問題

有一些經(jīng)典的數(shù)學(xué)問題，使用遞歸函數(shù)來解決都非常方便。階乘就是這樣一個典型的問題，清單 5 給出了一個實(shí)現(xiàn)階乘計(jì)算的 bash 腳本（當(dāng)然，除了使用遞歸函數(shù)之外，簡單地利用一個循環(huán)也可以實(shí)現(xiàn)計(jì)算階乘的目的，不過本文以此為例來介紹遞歸函數(shù)的相關(guān)問題）。

清單5. 階乘函數(shù)的 bash 實(shí)現(xiàn)

[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

這個腳本看上去并沒有什么問題：遞歸函數(shù)的參數(shù)傳遞和普通函數(shù)沒什么不同，返回值是通過獲取 $? 的值實(shí)現(xiàn)的，這是利用了執(zhí)行命令的退出碼。然而，最終的結(jié)果卻顯然是錯誤的。調(diào)試一下就會發(fā)現(xiàn)，當(dāng)遞歸回溯到盡頭時，變量 i 的值被修改為 0；而退出上次函數(shù)調(diào)用之后，變量 i 的新值也被帶了回來，詳細(xì)信息如清單 6 所示（請注意黑體部分）。

清單6. 調(diào)試 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 腳本中，不管是否在函數(shù)中定義，變量默認(rèn)就是全局的，一旦定義之后，對于此后執(zhí)行的命令全部可見。bash 也支持局部變量，不過需要使用 local 關(guān)鍵字進(jìn)行顯式地聲明。local 是bash 中的一個內(nèi)嵌命令，其作用是將變量的作用域設(shè)定為只有對本函數(shù)及其子進(jìn)程可見。局部變量只能在變量聲明的代碼塊中可見，這也就意味著在函數(shù)內(nèi)聲明的局部變量只能在函數(shù)代碼塊中才能被訪問，它們并不會污染同名全局變量。因此為了解決上面這個程序的問題，我們應(yīng)該使用 local 關(guān)鍵字將 i 聲明為局部變量。修改后的腳本如清單 7 所示。

清單7. 遞歸函數(shù)中使用 local 關(guān)鍵字聲明局部變量

[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 的階乘計(jì)算對了，但是稍微大一點(diǎn)的數(shù)字都會出錯，比如 6 的階乘計(jì)算出來是錯誤的 208。這個問題的原因在于腳本中傳遞函數(shù)返回值的方式存在缺陷，$? 所能傳遞的最大值是 255，超過該值就沒有辦法利用這種方式來傳遞返回值了。解決這個問題的方法有兩種，一種是利用全局變量，另外一種則是利用其他方式進(jìn)行周轉(zhuǎn)（例如標(biāo)準(zhǔn)輸入輸出設(shè)備）。清單 8 和清單 9 分別給出了這兩種方法的參考實(shí)現(xiàn)。

清單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. 利用標(biāo)準(zhǔn)輸入輸出設(shè)備傳遞返回值

[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

盡管利用全局變量或標(biāo)準(zhǔn)輸入輸出設(shè)備都可以解決如何正確傳遞返回值的問題，但是它們卻各有缺點(diǎn)：如果利用全局變量，由于全局變量對此后的程序全部可見，一旦被其他程序修改，就會出錯，所以編寫代碼時需要格外小心，特別是在編寫復(fù)雜的遞歸程序的時候；如果利用標(biāo)準(zhǔn)輸入輸出設(shè)備，那么遞歸函數(shù)中就存在諸多限制，例如任何地方都不能再向標(biāo)準(zhǔn)輸出設(shè)備中打印內(nèi)容，否則就可能被上一層調(diào)用當(dāng)作正常輸出結(jié)果讀走了，另外速度方面也可能存在嚴(yán)重問題。

參數(shù)傳遞問題

在設(shè)計(jì)函數(shù)時，除了返回值之外，我們可能還希望所調(diào)用的函數(shù)還能夠返回其他一些信息。例如，在上面的階乘遞歸函數(shù)中，我們除了希望計(jì)算最后的結(jié)果之外，還希望了解這個函數(shù)一共被調(diào)用了多少次。熟悉 c 語言之類的讀者都會清楚，這可以通過傳遞一個指針類型的參數(shù)實(shí)現(xiàn)。然而，在 bash 中并不支持指針，它提供了另外一種在解釋性語言中常見的設(shè)計(jì)：間接變量引用（indirect variable reference）。讓我們看一下下面這個例子：

var2=$var3
var1=$var2

其中變量 var2 的存在實(shí)際上就是為了讓 var1 能夠訪問 var3，實(shí)際上也可以通過 var1 直接引用 var3 的值，方法是 var1=\$$var3（請注意轉(zhuǎn)義字符是必須的，否則 $$ 符號會被解釋為當(dāng)前進(jìn)程的進(jìn)程 ID 號），這種方式就稱為間接變量引用。從 bash2 開始，對間接變量引入了一種更為清晰的語法，方法是 var1=${!var3}。

清單 10 中給出了使用間接變量引用來統(tǒng)計(jì)階乘函數(shù)被調(diào)用次數(shù)的實(shí)現(xiàn)。

清單10. 利用間接變量引用統(tǒng)計(jì)遞歸函數(shù)的調(diào)用次數(shù)

[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.

在上面我們曾經(jīng)介紹過，為了解決變量作用域和函數(shù)返回值的問題，在遞歸函數(shù)中我們使用 local 聲明局部變量，并采用全局變量來傳遞返回值。但是隨著調(diào)用關(guān)系變得更加復(fù)雜，全局變量的值有可能在其他地方被錯誤地修改。實(shí)際上，使用局部變量也存在一個問題，下面讓我們來看一下清單 11 中給出的例子。

清單11. 查找字符串在文件中是否存在，并計(jì)算所在行數(shù)和出現(xiàn)次數(shù)

[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]#

這段程序的目的是查找某個字符串在指定文件中是否存在，如果存在，就計(jì)算第一次出現(xiàn)的行數(shù)和總共出現(xiàn)的次數(shù)。為了說明局部變量和后面提到的子函數(shù)的問題，我們故意將對出現(xiàn)次數(shù)的打印也放到了 GetLine 函數(shù)之外進(jìn)行處理。清單 11 中全部使用全局變量，并沒有出現(xiàn)什么問題。下面讓我們來看一下將 GetLine 中使用的局部變量改用 local 聲明后會出現(xiàn)什么問題，修改后的代碼和執(zhí)行結(jié)果如清單 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 的運(yùn)行結(jié)果顯示，在文件中搜索 six 關(guān)鍵字時的結(jié)果是錯誤的，調(diào)試會發(fā)現(xiàn)，問題的原因在于：第 8 行使用 local 將 line 聲明為局部變量，并將 grep 命令的執(zhí)行結(jié)果賦值給 line 變量。然而不論 grep 是否成功在文件中找到匹配項(xiàng)（grep 程序找到匹配項(xiàng)返回值為 0，否則返回值為 1），第 9 行中 ? 的值實(shí)際上是執(zhí)行 local 命令的返回值，不管 grep 命令的結(jié)果如何，它總是 0。

要解決這個問題，可以將第 8 行的命令拆分開，首先使用單獨(dú)一行將變量 line 聲明為 local的，然后再執(zhí)行這條 grep 命令，并將結(jié)果賦值給變量 line（此時前面不能加上 local）。

解決變量作用域的另外一種方法是使用子 shell。所謂子 shell 是在當(dāng)前 shell 環(huán)境中啟動一個子 shell 來執(zhí)行所調(diào)用的命令或函數(shù)，這個函數(shù)中所聲明的所有變量都是局部變量，它們不會污染原有 shell 的名字空間。清單 13 給出了使用子 shell 修改后的例子。

清單13. 利用子 shell 實(shí)現(xiàn)局部變量

[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 函數(shù)并不需要任何變化，變量定義和程序調(diào)用都沿用正常方式。唯一的區(qū)別在于調(diào)用該函數(shù)時，要將其作為一個子 shell 來調(diào)用（請注意第 37 行兩邊的圓括號）。另外一個問題是在子 shell 中修改的所有變量對于原有 shell 來說都是不可見的，這也就是為什么在第 38 行要通過 $? 來檢查返回值，而 rtn 變量的值卻是錯誤的。另外由于 num 在 GetLine 函數(shù)中也被當(dāng)作是局部變量，同樣無法將修改后的值傳出來，因此也并沒有打印所匹配到的 line 的數(shù)目是 3 行的信息。

解決上面這個問題就只能使用前面提到的利用標(biāo)準(zhǔn)輸入輸出設(shè)備的方法了，否則即使使用間接變量引用也無法正常工作。清單 14 給出了一個使用間接變量引用的例子，盡管我們使用不同的名字來命名全局變量和局部變量，從而確保不會引起同名混淆，但是依然無法正常工作。原因同樣在于 GetLine 函數(shù)是在另外一個子進(jìn)程中運(yùn)行的，它對變量所做的更新隨著子 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 腳本可以實(shí)現(xiàn)遞歸函數(shù)，但是由于先天性的不足，使用 bash 腳本編寫的遞歸函數(shù)的性能都比較差，問題的根本在于它的主要流程都是要不斷地調(diào)用其他程序，這會 fork 出很多進(jìn)程，從而極大地增加運(yùn)行時的開銷。下面讓我們來看一個計(jì)算累加和的例子，清單 15 和清單 16 給出了兩個實(shí)現(xiàn)，它們分別利用全局變量和標(biāo)準(zhǔn)輸入輸出設(shè)備來傳遞返回值。為了簡單起見，我們也不對輸入?yún)?shù)進(jìn)行任何判斷。

清單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. 累加和，利用標(biāo)準(zhǔn)輸入輸出設(shè)備傳遞返回值

[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

下面讓我們來測試一下這兩個實(shí)現(xiàn)的性能會有多大的差距：

清單17. 利用全局變量和標(biāo)準(zhǔn)輸入輸出設(shè)備傳遞返回值的性能比較

[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

在計(jì)算 1 到 500 的累加和時，利用標(biāo)準(zhǔn)輸入輸出設(shè)備傳遞返回值的方法速度要比利用全局變量慢 1 倍以上。隨著迭代次數(shù)的增加，二者的差距也會越來越大，主要原因標(biāo)準(zhǔn)輸入輸出設(shè)備都是字符設(shè)備，從中讀寫數(shù)據(jù)耗時會很長；而全局變量則是在內(nèi)存中進(jìn)行操作的，速度會明顯快很多。

為了提高 shell 腳本的性能，在編寫 shell 腳本時，應(yīng)該盡量多使用 shell 的內(nèi)嵌命令，而不能過多地調(diào)用外部腳本或命令，因?yàn)檎{(diào)用內(nèi)嵌命令時不會 fork 新的進(jìn)程，而是在當(dāng)前 shell 環(huán)境中直接執(zhí)行這些命令，這樣可以減少很多系統(tǒng)開銷。以計(jì)算表達(dá)式的值為例，前面的例子我們都是通過調(diào)用 expr 來對表達(dá)式進(jìn)行求值的，但是 bash 中提供了一些內(nèi)嵌的計(jì)算表達(dá)式手段，例如 ((i = k)) 與 i=expr $j + $k 的效果就是完全相同的，都是計(jì)算變量 j 與 k 的值，并將結(jié)果賦值給變量 i，但是前者卻節(jié)省了一次 fork 新進(jìn)程以及執(zhí)行 expr 命令的開銷。下面讓我們對清單 15 中的腳本進(jìn)行一下優(yōu)化，如清單 18 所示。

清單18. 優(yōu)化后的計(jì)算累加和的腳本

[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

現(xiàn)在讓我們來比較一下優(yōu)化前后的性能差距，如清單 19 所示。

清單19. 優(yōu)化前后的性能對比

[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 次時，優(yōu)化后的腳本速度要比優(yōu)化前快 5 倍以上。但是無論如何，使用 shell 腳本編寫的遞歸函數(shù)的執(zhí)行效率都不高，c 語言的實(shí)現(xiàn)與其相比，快了可能都不止一個數(shù)量級，詳細(xì)數(shù)據(jù)請參看清單 20。

清單20. c 語言與 bash 腳本實(shí)現(xiàn)遞歸函數(shù)的對比

[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

因此，如果編寫對性能要求很高的遞歸程序，還是選擇其他語言實(shí)現(xiàn)好了，這并不是 shell 的強(qiáng)項(xiàng)。

小結(jié)

本文從經(jīng)典的 fork 炸彈遞歸函數(shù)入手，逐一介紹了在 bash 中編寫遞歸函數(shù)時需要注意的問題，包括返回值、參數(shù)傳遞和性能等方面的問題以及解決方法，并對如何提高 shell 腳本性能提供了一個建議。

下載

• 請下載本文中使用的所有腳本文件 recursion_in_bash.tar.gz 。

相關(guān)主題

• 請?jiān)L問 bash 的主頁，從這里可以獲得最新版本的 bash 源代碼以及詳細(xì)的手冊。
• Shell 腳本調(diào)試技術(shù)一文中介紹了常用的一些 shell 腳本調(diào)試方法。
• 希望擁有一個像 gdb 一樣功能強(qiáng)大的 shell 腳本調(diào)試器嗎？bashdb 就是最好的選擇，詳細(xì)信息請參看bashdb 的主頁。