Bash Script - Fibonacci

Shell Script to Generate Fibonacci Series

There are two problems here. First, all of your variables are global, which means that when you make a recursive call it overwrites the values of nr, rez, rez1, and rez2. You can fix this by declaring them as local:

fib() {
    local nr rez rez1 rez2
    if [ $1 -eq 1 -o $1 -eq 2 ]; then
        return 1
    else
        let nr=$1-1
        fib $nr
        rez1=$?
        let nr=$1-2
        fib $nr
        rez2=$?
        let rez=$rez1+$rez2
        return $rez
    fi
}

The second problem is that you're trying to pass a number via the return status of the function. The return status is a 1-byte unsigned integer, which means it can't get bigger than 255 (after which it wraps around to 0. It's really intended to give success/failure results (and maybe some information about what failed), with 0 indicating success and anything else indicating an error. Trying to use it for something else is asking for trouble. You can see the results here (from the localized version of the function):

$ fib 11; echo $?
89
$ fib 12; echo $?
144
$ fib 13; echo $?
233
$ fib 14; echo $?
121

The 14th Fibonacci number is 377, but that's over 255 so it came out as 377-256 = 121. To fix this, return the result by echoing it to stdout and capture it with $( ):

fib() { 
    local nr rez rez1 rez2
    if [ $1 -eq 1 -o $1 -eq 2 ]; then
        echo 1
    else
        let nr=$1-1
        rez1=$(fib $nr)
        let nr=$1-2
        rez2=$(fib $nr)
        let rez=$rez1+$rez2
        echo $rez
    fi
}

...this does have a disadvantage, though: it's much slower, because every call to fib has to run as a subprocess, and creating subprocesses is computationally expensive. (This actually would've solved the global-variable problem, since variables inherit down to subprocesses but not up from them; but it only solves it by accident.)

Take-home lesson: shell scripts aren't the right language for things like this.

Recursive Fibonacci in Bash script

As Wumpus said you need to produce output using for example echo.
However you also need to fix the recursive invocation.
The outermost operation would be an addition, that is you want:

echo $(( a + b ))

Both a and b are substitutions of fibonacci, so

echo $(( $(fibonacci x) + $(fibonacci y) ))

x and y are in turn arithmetic expressions, so each needs its own $(( )), giving:

echo $(( $(fibonacci $((first-1)) ) + $(fibonacci $((second-2)) ) ))

If you are confused by this, you should put the components into temporary variables and break down the expression into parts.

As to the actual fibonacci, it's not clear why you are passing 2 arguments.

Bash Script - Fibonacci

There are a couple of issues with your code. You cannot use $? for any useful arithmetic because the number wraps around at 255. And the embedded $((...)) is not useful at all -- you are already in arithmetic context inside the double parentheses.

#!/bin/bash

fib()
{
  local number term1 term2 # Avoid leaking to main scope
  number=$1
  if ((number < 2))
    then
      ((tmp=number))
  else
      ((--number))
      term1=$(fib "$number")
      ((--number))
      term2=$(fib "$number")
      ((tmp=term1+term2))
  fi
  ((result=result+tmp))
  printf '%s\n' "$result"
}

#Main Program.
fib "$1"   # Quote argument properly!

Inside the (( arithmetic parentheses )) you don't need the $ in front of variables; it's harmless, but you should probably try to be consistent.

As with any naïve Fibonacci implementation, this is hugely inefficient. It would be smarter to calculate the head of the sequence once in a helper function, then pull the final result and display it.

#!/bin/bash

fib2() {
    local f
    ((f=$1+$2))
    printf '%i %i\n' "$f" "$1"
}

fib()
{
    local i j
    j=$1
    shift
    for((i=1; i<j; ++i)); do
        set -- $(fib2 ${1-1} ${2-0})
    done
    printf '%s\n' "${1-$i}"
}

#Main Program.
fib "$1"

How to code the program in the Shell Script

$ cat fib
#!/bin/bash
Num=${1-5}
a=0
b=1
unset s

printf "Result: "
for (( i=0; i<Num; i++ )); do
    printf "${s:+ + }$a"
    s=$(($s + $a))
    n=$((a+$b))
    a=$b
    b=$n
done
echo " = $s"
$ ./fib 5
Result: 0 + 1 + 1 + 2 + 3 = 7
$ ./fib 10
Result: 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 = 88

Print Fibonacci series using recursion in bash with only 1 variable

Just for (my kind of) fun, this code prints the Fibonacci numbers from the 0th to the 92nd (as defined in Fibonacci number - Wikipedia) with a recursive function that uses no variables:

#! /bin/bash

function fib
{
    echo ${3-0}

    (($1 > 0)) && fib $(($1-1)) ${3-0} $((${2-1}+${3-0}))
}

fib 92

Some may claim that using the positional parameters ($1, $2, $3) for this is cheating, but then other solutions could be said to be using two variables ($i and $1).

The code takes under 0.01 seconds to run on my (oldish) Linux machine.

The code should work with numbers up to 92 with Bash version 3 or later on any platform. See Bash Number Limit?. Numbers higher than 93 will cause to code to produce garbage results due to arithmetic overflow.

---

Related Topics