用 bash 算費氏數列，就當了 - Linux

※ 引述《Gold740716 (項為之強)》之銘言：
: febo(){
: i=$1
: (( j = i-1 , k = i-2 ))
:
: if (( i <= 1 ))
: then
: echo 1
: else
: echo $(expr `febo $j` + `febo $k` )
: fi
: }
:
:
: 邏輯問題是 febo 1 和 febo 0 都回傳 1 ，
: 所以 febo 2 = 2 ，也就是我第 0 項變成 1 ；而不是 0 。
: 我想知道 fork 炸彈在哪，小弟功力不足。
:
: -------------------------------
: x | 0 1 2 3 4 5 6
: --------+----------------------
: febo x | 1 1 2 3 5 8 13
: -------------------------------
:

都已經知道了, 所以就不要偷懶, 讓 0 echo 0 不就好了?

febo(){
i=$1
(( j = i-1 , k = i-2 ))

if [ $i -eq 0 ]
then
echo 0
elif [ $i -eq 1 ]
then
echo 1
else
echo $(expr `febo $j` + `febo $k`)
fi
}

然後你可以算一下, 每呼叫一次,
0 & 1 會呼叫 echo
>1 時會呼叫 echo 跟 expr 各一次.

小弟個人不喜歡用 bash 專有的 (( )) 跟 $() 來寫 script.
不知道(()) 跟 $() 會不會 fork 子程序?

50 會呼叫 49/48, 49 會呼叫 48/47
也就是 50 第 1 次被呼叫,接著
49 會被呼叫 1 次
48 被呼叫 2 次 (50 跟 49)
47 被呼叫 3 次 (49 跟 48)
46 被呼叫 5 次 (48 跟 47)
45 被呼叫 8 次 (47 跟 46)
依此類推. 總共會被呼叫... 剛好跟費式數列一樣的次數 (之前的推文算錯了...)
而這些程序在數列算完之前都不會結束 (遞迴的特性), 所以要累加起來.

0 & 1 共有 32,951,280,099 次
>1 的共有 20,365,011,073 次
總共會 fork 出 73,681,302,245 個子程序

所以, 你現在可以原諒系統當掉了嗎?

還是用一般迴圈來算吧.

fibo[0]=0
fibo[1]=1
i=2
while [ $i -le $1 ]
do
fibo[$i]=`expr ${fibo[$i-1]} + ${fibo[$i-2]}`
i=`expr $i + 1`
done
echo ${fibo[$1]}

不過費式不拿來練習遞迴, 光算出值好像沒啥用...
而且超過 92 位, expr 就 overflow 了... 哈哈

Rickie MBPr:0 rickie$ time ./go.sh 92
7540113804746346429

real 0m0.386s
user 0m0.155s
sys 0m0.221s

Rickie MBPr:0 rickie$ time ./go.sh 93
expr: overflow


real 0m0.415s
user 0m0.163s
sys 0m0.241s

--