bash(awk遞歸)N階【斐波那契數列】多種實現(含遞歸解析圖)

【版權所有】轉載請說明作者【Jev Tes】
       【本文導航】
       零、關于斐波那契數列
       一、輸入參數合法性判斷
       二、TYP 1：常規累加法
       三、TYP 2：數組傳遞法
       四、TYP 3：遞歸法
           1、shell遞歸
           2、awk優化遞歸
       五、效率比較

零、關于斐波那契數列
    斐波那契數列又稱黃金分割數列，因數學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列： 0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 ……，這個數列從第3項開始，每一項都等于前兩項之和。
    斐波納契數列以如下被以遞歸的方法定義： F（0）=0， F（1）=1， F（n）=F(n-1)+F(n-2)（ n≥2）

一、輸入參數合法性判斷

    編寫腳本/函數時，對輸入參數合法性的判斷非常重要，可以規避很多不必要的麻煩，特別是調試遞歸函數時！

#--------------------------------輸入參數合法性判斷--------------------------------
if ! echo $1 | egrep "^[0-9]+$"  &> /dev/null ; #如果輸入不是0或正整數，執行下面語句
then
    echo "-Fib 119:error token is \""$1"\"!"   #回顯錯誤信息
    exit 110                     #退出腳本
fi
#------------------------------------------------------------------------------

二、TYP 1：常規累加法
    整體思路：從第3階開始計算F3=F2+F1=1+1=2、F4=F3+F2=2+1=3…依次計算到第N階；
    主體代碼跟分析如下：

#--------------------------------累加算法--------------------------------
fib()                             #定義函數
 { 
local i=2                         #本地變量，做計數用
local Fib0=0                      #本地變量，記錄傳遞F(n-2)的值，初始值為F0的值
local Fib1=1                      #本地變量，記錄傳遞F(n-1)的值，初始值為F1的值
local $Fibn                       #本地變量，記錄傳遞F(n)的值
[ $1 -eq 0  ] && echo "F(0)=0" && return 0  #如果$1值為0，直接回顯F(0)=0，退出函數
[ $1 -eq 1  ] && echo "F(1)=1" && return 1  #如果$1值為1，直接回顯F(1)=1，退出函數
until  [ $i -gt $1  ] ; do        #當$i大于$1(計算階數)時，退出循環
Fibn=$[Fib1+Fib0]                 #Fn=F(n-1) +F(n-2)，n為此時$i的值
Fib0=$Fib1                        #將當前F(n-1)的值，即為下輪F(n-2)的值
Fib1=$Fibn                        #將當前F(n)的值，即為下輪F(n-1)的值
i=$[i+1]                          #對$i進行累加1
done 
echo  "F("$1")=$Fibn"             #退出循環后，輸出Fn的值
 }
fib $1                            #引用函數

三、TYP 2：數組傳遞法
    整體思路：跟常規累加傳遞法類似，從第3階開始計算，依次計算到第N階，但這方法奇妙在于用數組來儲存整個數列，可以將整個數列完整保存下來；
    主體代碼跟分析如下：

#--------------------------------數組傳遞法--------------------------------
fib()                        #定義函數
{
declare -a Fib               #定義數組Fib
Fib[0]=0                     #賦值F0=0
Fib[1]=1                     #賦值F1=1
Fib[2]=1                     #賦值F1=1
case $1 in
0)
    echo ${Fib[0]}           #如果$1值為0，直接回顯F(0)=0
    ;; 
1)
    echo ${Fib[1]}           #如果$1值為0，直接回顯F(0)=0
    ;;
*)
    for i in `seq 2 $1`;do   #$i在2-$1時進行循環
    Fib[$i]=$[${Fib[$i-1]}+${Fib[$i-2]}]  #Fib[$i]的值為前兩項的值之和
    done
    echo ${Fib[$1]}          #退出循環后，輸出Fn的值
    ;;
esac
}
fib $1                       #引用函數

四、TYP 3：遞歸法
   整體思路：跟以上倆種思路相反，函數從N階開始，依次向下遞歸展開，直到$1=1,$1=0,時停止遞歸，并將值回傳給父函數；
   主體代碼跟分析如下：
       1、shell遞歸 

#-------------------------------shell遞歸---------------------------------
Fib()                         #定義函數 
{ if [ $1 -eq 0 ]  ;
then   echo 0                   #當$1值為0，回顯0
elif [ $1 -eq 1 ]  ;then   echo 1     #當$1值為0，回顯1
else   echo $[$(Fib $[$1-1])+$(Fib $[$1-2])]    
 #遞歸展開Fn=F(n-1)+F(n-2)直到$[$1-1]=1,$[$1-2]=0，遞歸終止fi} 
Fib $1                       #引用函數

       2、awk優化遞歸 

#--------------------------------awk遞歸算法--------------------------------
awk -v i=$1  'function Fib(i){
if(i==0){ return 0}               #當$i值為0，返回0
else if(i==1){return 1}           #當$i值為0，返回0
else{return Fib(i-1)+Fib(i-2)}    #展開遞歸，計算Fib(i-1)+Fib(i-2)的值
}BEGIN{ print Fib(i)}'

簡單遞歸思路解析：（以4階為例，即$1=4）
F4=F3+F2 
    =(F2+F1)+(F1+F0)      
    =[(F1+F0)+F1]+(F1+F0) 
    =3F1+2F0 
    =3
   遞歸解析圖如下：（以4階為例，即$1=4）
   

五、效率比較
   測試環境
   虛擬平臺：VMware
   虛擬機系統：centos6.8
   虛擬機配置：CPU*2(宿主主機CPUI56300)，內存1664MB
簡單測試結果如下：
     常規累加法
   
     數組傳遞法
   
     shell遞歸
   
     awk優化遞歸
   
   從這個簡單的測試可以得出：
    從算法角度來說，直接累加運算效率最高，數組傳遞算法略遜些，由于遞歸比較耗資源，效益最低；
    從計算速度來講awk計算高于bash計算；
注：遞歸計算時間與資源消耗都隨著階數的變化呈指數性增長
    

【點擊返回頁首】

【版權所有】轉載請說明作者【Jev Tes】