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】