Shell script to generate Fibonacci series using recursion

I am facing problem with Shell script to generate Fibonacci series using recursion i.e. recursive function.
Here is my script:

#!/bin/sh

fibo()
{
    no=$1
    if [ $no -eq 1 ]; then
        return 0
    elif [ $no -eq 2 ]; then
        return 1
    else
        a1=`expr $no - 1`
        fibo $a1
        a=$(echo $?)

        b1=`expr $no + 1`
        fibo $b1
        b=$(echo $?)

        c=`expr $a + $b`
        return $c
    fi
}

####### Main

clear

echo -e "Enter number of terms : \c"
read n

if [ $n -gt 0 ]; then
    for (( i=1; i<=$n; i++ ))
    do
        fibo $i
        echo $?    
    done
else
    echo -e "Invalid input."
fi

But it does not give output.
Please help...

I don't think you can call function within the function

Thank you sir for your reply. I have a program to generate factorial of a number solved by recursion where I called the fact() function within fact().

---------- Post updated at 07:23 PM ---------- Previous update was at 01:31 PM ----------

At last it is solved.

#!/bin/sh

# Shell scrpt to generate Fibonacci series using recursion

export MINIDX=2                     

Fibonacci ()
{
    idx=$1                
    if [ "$idx" -lt "$MINIDX" ]; then
        echo "$idx"              
    else
        (( --idx ))              
        term1=$( Fibonacci $idx )       

        (( --idx ))              
        term2=$( Fibonacci $idx )       

        echo $(( term1 + term2 ))
    fi
}

echo -n "Enter the number of term : "
read MAXTERM

for (( i=0; i<=$MAXTERM; i++ ))
do                      
    FIBO=$(Fibonacci $i)
    echo -n "$FIBO "
done

echo

exit 0

Good try, the code run very slow, can anyone optimize it?

$ ./your_script
Enter the number of term : 10
0 1 1 2 3 5 8 13 21 34 55

I guess recursion is a requirement? It sure seems inefficient.

Your script using recursion:

$ time ./fibo2.sh
Enter the number of term : 10
0 1 1 2 3 5 8 13 21 34 55

real    0m14.875s
user    0m8.454s
sys     0m4.765s

Mine not using recursion:

$ time ./fibo.sh
Enter the number of term : 10
Fibonacci (10)=55

real    0m1.817s
user    0m0.046s
sys     0m0.030s

Another recursive one:

#!/bin/ksh

function Fibonacci {
  case $1 in
    0|1) printf "$1 " ;;
    *)   printf "$(( $(Fibonacci $(($1-2))) + $(Fibonacci $(($1-1))) )) ";;
  esac
}

for (( i=0; i<=$1; i++ )); do
  Fibonacci $i
done
echo

$ time ./test 10
0 1 1 2 3 5 8 13 21 34 55

real    0m0.086s
user    0m0.072s
sys     0m0.012s

(On a pentium III 850 MHz)

With the OP's script I get similar numbers if I leave out the read statement

Wow quite interesting results. Wonder if its some oddity because I am running this in cygwin. I am using a centrino2 vpro2

I changed the 3 scripts to use $1 instead of a read and the times required are vastly different.

None recursive script I threw together:
$ time ./fibo.sh 10
Fibonacci (10)=55

real    0m0.055s
user    0m0.046s
sys     0m0.030s

Original script from post #2:
$ time ./fibo2.sh 10
0 1 1 2 3 5 8 13 21 34 55

real    0m18.554s
user    0m8.199s
sys     0m4.926s

Script posted by scrutinizer in post #6, well I had to slightly change your while loop cause my shell 
could not digest the inline declaration of "i" so mine looks like this at the bottom of the file:
while [ $i -lt $1 ]
do
let i=i+1
  Fibonacci $i
done
echo

$ time ./fibo3.sh 10
1 1 2 3 5 8 13 21 34 55

real    0m11.508s
user    0m7.953s
sys     0m4.610s

Yes, the recursive approach is not the most efficient way. What is also interesting is the difference between shells. I changed your code yet again a bit so that it would work in any posix shell:

Fibonacci (){
  case $1 in
    0|1) printf "$1 " ;;
    *)   printf "$(( $(Fibonacci $(($1-2))) + $(Fibonacci $(($1-1))) )) ";;
  esac
}

i=0
while [ $i -lt $1 ]
do
  i=$((i+1))
  Fibonacci $i
done
echo

I tested it with bash zsh, dash and ksh:

$ time ./testzsh 10
1 1 2 3 5 8 13 21 34 55

real    0m0.837s
user    0m0.180s
sys     0m0.648s
$ time ./testbash 10
1 1 2 3 5 8 13 21 34 55

real    0m0.887s
user    0m0.300s
sys     0m0.580s
$ time ./testdash 10
1 1 2 3 5 8 13 21 34 55

real    0m0.292s
user    0m0.048s
sys     0m0.240s
$ time ./testksh 10
1 1 2 3 5 8 13 21 34 55

real    0m0.092s
user    0m0.088s
sys     0m0.000s

As is my usual experience, ksh is quite a bit faster then other shells.

I also tested a nonrecursive version (timed in ksh):

$ time ./nonrecurs 10
0 1 1 2 3 5 8 13 21 34 55

real    0m0.013s
user    0m0.016s
sys     0m0.000s

And the difference will become vast once the number goes to 20 and higher.

I found this one on my notes

#!/bin/sh
fibonnacci()
{
        case $n in
                0) echo 0;      return;;
                1) echo 0 1;    return;;
                *) echo -n 0 1
                                a=0; b=1; c=2;
                                while [ $c -le $n ]
                                do
                                        t=$(( a + b ))
                                        echo -n " $t"
                                        a=$b; b=$t;
                                        c=$(( c + 1 ))
                                done
                                echo
                                return;;
        esac
}
#
n=${1:-10}
if [ ! `expr $n + 1 2> /dev/null` ] ; then
        echo "Value of the arguments < $n > IS NOT an integer!"
        exit 1
fi
echo "Fibonnacci series for value $n is:"
fibonnacci $n
exit 0

Computing Fibonacci series via recursion is (because each new element n needs two passes of the algorithm, one for n-1 and one for n-2) not the best idea, to put it mildly. It is easy to show that the Landau-symbol for the runtime characteristics of this algorithm is:

(Basically it means that the time necessary to compute some x will be doubled when x increases by 1.)

The main difference between the original and the improved version was:

x=`expr $x - 1`

and

(( x = x - 1 ))

The reason for this is the fact that "expr" is an external program the shell has to call via the "fork()" system call, which is time intensive. The second variant is completely internal and doesn't need to call an external program so this overhead is removed. The Landau-symbol for the runtime characteristics is still the same as above.

The most efficient implementation is non-recursive and probably something like:

#!/bin/ksh

fibonacci ()
{
typeset -i iStopAt=$1
typeset -i iFibLast1=1
typeset -i iFibLast2=0
typeset -i iFibCurrent=1
typeset -i iCurrIndex=1

while [ $iCurrIndex -le $iStopAt ] ; do
     (( iFibCurrent = iFibLast1 + iFibLast2 ))
     iFibLast2=iFibLast1
     iFibLast1=iFibCurrent
     (( iCurrIndex += 1 ))
done

print - "$iFibCurrent"
return 0
}

# main ()
iCnt=1

while [ iCnt -le 25 ] ; do
     fibonacci $iCnt
     (( iCnt += 1 ))
done
exit 0

I hope this helps.

bakunin

I made the following non-recursive alternative to use with the tests:

#!/bin/ksh

Fibonacci (){
  for (( i=0; i<=$1; i++ )); do
    case $i in
      0|1) val=$i ;;
      *)   val=$((val1 + val2));;
    esac
    printf "$val "
    val2=$val1
    val1=$val
  done
}

Fibonacci $1
echo