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

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

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

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

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

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

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

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

清單1. bash 中的 fork 炸彈

.(){ .|.& };.

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

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

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

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

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

• 關(guān)鍵字单默，例如 if碘举、for 等。
• 別名搁廓。別名不能與關(guān)鍵字相同引颈，但是可以為關(guān)鍵字定義別名，例如 end=fi境蜕。
• 特殊內(nèi)嵌命令蝙场，例如 break、continue 等粱年。POSIX 定義的特殊內(nèi)嵌命令包括：.（小數(shù)點(diǎn)）售滤、:（冒號(hào)）、break台诗、continue完箩、eval、exec拉队、exit弊知、export、readonly粱快、return秩彤、set、shift事哭、times漫雷、trap 和 unset。bash 又增加了一個(gè)特殊的內(nèi)嵌命令 source慷蠕。
• 函數(shù)珊拼。如果處于非 POSIX 模式，bash 會(huì)優(yōu)先匹配函數(shù)流炕，然后再匹配內(nèi)嵌命令澎现。
• 非特殊內(nèi)嵌命令仅胞，例如 cd、test 等剑辫。
• 腳本和可執(zhí)行程序干旧。在 PATH 環(huán)境變量指定的目錄中進(jìn)行搜索，返回第一個(gè)匹配項(xiàng)妹蔽。

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

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

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

清單3. bash 與 sh 對(duì)命令匹配順序的區(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 炸彈捂刺，會(huì)以2的指數(shù)次冪的速度不斷產(chǎn)生新進(jìn)程，這會(huì)導(dǎo)致系統(tǒng)資源會(huì)被迅速耗光募寨，最終除非重新啟動(dòng)機(jī)器族展，否則基本上就毫無辦法了。為了防止這會(huì)造成太大的損害拔鹰，我們可以使用 ulimit 限制每個(gè)用戶能夠創(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 炸彈會(huì)迅速 fork 出大量進(jìn)程宾茂，此后會(huì)由于資源不足而無法繼續(xù)執(zhí)行。

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

返回值問題

有一些經(jīng)典的數(shù)學(xué)問題弓摘，使用遞歸函數(shù)來解決都非常方便焚鹊。階乘就是這樣一個(gè)典型的問題，清單 5 給出了一個(gè)實(shí)現(xiàn)階乘計(jì)算的 bash 腳本（當(dāng)然衣盾，除了使用遞歸函數(shù)之外寺旺，簡(jiǎn)單地利用一個(gè)循環(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

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

清單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)就是全局的，一旦定義之后湖员，對(duì)于此后執(zhí)行的命令全部可見贫悄。bash 也支持局部變量，不過需要使用 local 關(guān)鍵字進(jìn)行顯式地聲明娘摔。local 是bash 中的一個(gè)內(nèi)嵌命令窄坦，其作用是將變量的作用域設(shè)定為只有對(duì)本函數(shù)及其子進(jìn)程可見。局部變量只能在變量聲明的代碼塊中可見，這也就意味著在函數(shù)內(nèi)聲明的局部變量只能在函數(shù)代碼塊中才能被訪問鸭津，它們并不會(huì)污染同名全局變量彤侍。因此為了解決上面這個(gè)程序的問題，我們應(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ì)算對(duì)了，但是稍微大一點(diǎn)的數(shù)字都會(huì)出錯(cuò)父泳，比如 6 的階乘計(jì)算出來是錯(cuò)誤的 208般哼。這個(gè)問題的原因在于腳本中傳遞函數(shù)返回值的方式存在缺陷，$? 所能傳遞的最大值是 255惠窄，超過該值就沒有辦法利用這種方式來傳遞返回值了蒸眠。解決這個(gè)問題的方法有兩種，一種是利用全局變量杆融，另外一種則是利用其他方式進(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)：如果利用全局變量蒋腮，由于全局變量對(duì)此后的程序全部可見，一旦被其他程序修改藕各，就會(huì)出錯(cuò)池摧，所以編寫代碼時(shí)需要格外小心，特別是在編寫復(fù)雜的遞歸程序的時(shí)候激况；如果利用標(biāo)準(zhǔn)輸入輸出設(shè)備作彤，那么遞歸函數(shù)中就存在諸多限制，例如任何地方都不能再向標(biāo)準(zhǔn)輸出設(shè)備中打印內(nèi)容乌逐，否則就可能被上一層調(diào)用當(dāng)作正常輸出結(jié)果讀走了竭讳，另外速度方面也可能存在嚴(yán)重問題。

參數(shù)傳遞問題

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

var2=$var3
var1=$var2

其中變量 var2 的存在實(shí)際上就是為了讓 var1 能夠訪問 var3蓝翰，實(shí)際上也可以通過 var1 直接引用 var3 的值光绕，方法是 var1=\$$var3（請(qǐng)注意轉(zhuǎn)義字符是必須的，否則 $$ 符號(hào)會(huì)被解釋為當(dāng)前進(jìn)程的進(jìn)程 ID 號(hào)）畜份，這種方式就稱為間接變量引用诞帐。從 bash2 開始，對(duì)間接變量引入了一種更為清晰的語(yǔ)法爆雹，方法是 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.

在上面我們?cè)?jīng)介紹過钙态，為了解決變量作用域和函數(shù)返回值的問題慧起，在遞歸函數(shù)中我們使用 local 聲明局部變量，并采用全局變量來傳遞返回值册倒。但是隨著調(diào)用關(guān)系變得更加復(fù)雜蚓挤，全局變量的值有可能在其他地方被錯(cuò)誤地修改。實(shí)際上驻子，使用局部變量也存在一個(gè)問題灿意，下面讓我們來看一下清單 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]#

這段程序的目的是查找某個(gè)字符串在指定文件中是否存在缤剧，如果存在，就計(jì)算第一次出現(xiàn)的行數(shù)和總共出現(xiàn)的次數(shù)演熟。為了說明局部變量和后面提到的子函數(shù)的問題鞭执，我們故意將對(duì)出現(xiàn)次數(shù)的打印也放到了 GetLine 函數(shù)之外進(jìn)行處理。清單 11 中全部使用全局變量芒粹，并沒有出現(xiàn)什么問題兄纺。下面讓我們來看一下將 GetLine 中使用的局部變量改用 local 聲明后會(huì)出現(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)鍵字時(shí)的結(jié)果是錯(cuò)誤的，調(diào)試會(huì)發(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。

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

解決變量作用域的另外一種方法是使用子 shell。所謂子 shell 是在當(dāng)前 shell 環(huán)境中啟動(dòng)一個(gè)子 shell 來執(zhí)行所調(diào)用的命令或函數(shù)滤蝠，這個(gè)函數(shù)中所聲明的所有變量都是局部變量豌熄，它們不會(huì)污染原有 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ù)時(shí)芯肤，要將其作為一個(gè)子 shell 來調(diào)用（請(qǐng)注意第 37 行兩邊的圓括號(hào)）。另外一個(gè)問題是在子 shell 中修改的所有變量對(duì)于原有 shell 來說都是不可見的压鉴，這也就是為什么在第 38 行要通過 $? 來檢查返回值崖咨，而 rtn 變量的值卻是錯(cuò)誤的。另外由于 num 在 GetLine 函數(shù)中也被當(dāng)作是局部變量油吭，同樣無法將修改后的值傳出來击蹲，因此也并沒有打印所匹配到的 line 的數(shù)目是 3 行的信息。

解決上面這個(gè)問題就只能使用前面提到的利用標(biāo)準(zhǔn)輸入輸出設(shè)備的方法了婉宰，否則即使使用間接變量引用也無法正常工作歌豺。清單 14 給出了一個(gè)使用間接變量引用的例子，盡管我們使用不同的名字來命名全局變量和局部變量心包，從而確保不會(huì)引起同名混淆类咧，但是依然無法正常工作。原因同樣在于 GetLine 函數(shù)是在另外一個(gè)子進(jìn)程中運(yùn)行的蟹腾，它對(duì)變量所做的更新隨著子 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)用其他程序，這會(huì) fork 出很多進(jìn)程炉爆，從而極大地增加運(yùn)行時(shí)的開銷述寡。下面讓我們來看一個(gè)計(jì)算累加和的例子柿隙，清單 15 和清單 16 給出了兩個(gè)實(shí)現(xiàn)，它們分別利用全局變量和標(biāo)準(zhǔn)輸入輸出設(shè)備來傳遞返回值鲫凶。為了簡(jiǎn)單起見，我們也不對(duì)輸入?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

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

清單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 的累加和時(shí)艺晴，利用標(biāo)準(zhǔn)輸入輸出設(shè)備傳遞返回值的方法速度要比利用全局變量慢 1 倍以上昼钻。隨著迭代次數(shù)的增加，二者的差距也會(huì)越來越大封寞，主要原因標(biāo)準(zhǔn)輸入輸出設(shè)備都是字符設(shè)備然评，從中讀寫數(shù)據(jù)耗時(shí)會(huì)很長(zhǎng)；而全局變量則是在內(nèi)存中進(jìn)行操作的狈究，速度會(huì)明顯快很多碗淌。

為了提高 shell 腳本的性能，在編寫 shell 腳本時(shí)抖锥，應(yīng)該盡量多使用 shell 的內(nèi)嵌命令亿眠，而不能過多地調(diào)用外部腳本或命令，因?yàn)檎{(diào)用內(nèi)嵌命令時(shí)不會(huì) fork 新的進(jìn)程磅废，而是在當(dāng)前 shell 環(huán)境中直接執(zhí)行這些命令纳像，這樣可以減少很多系統(tǒng)開銷。以計(jì)算表達(dá)式的值為例拯勉，前面的例子我們都是通過調(diào)用 expr 來對(duì)表達(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 命令的開銷斗遏。下面讓我們對(duì)清單 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)化前后的性能對(duì)比

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

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

[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

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

小結(jié)

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

下載

• 請(qǐng)下載本文中使用的所有腳本文件 recursion_in_bash.tar.gz 九孩。

相關(guān)主題

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