Shell Script to Generate Fibonacci Series

Question

I am trying to make a recursive function to calculate the n-th number from Fibonnaci series. I already find a lot of solutions for this problem, but I what to know why mine doesn't work. Thanks.

function fib ()
{
        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
}

related: http://stackoverflow.com/q/17336915/632407 – clt60 Mar 23 '17 at 21:58 — clt60, Mar 23 '17 at 21:58

Gordon Davisson · Accepted Answer · 2017-03-24T01:37:47.617

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.

dawg · Answer 2 · 2017-03-24T02:38:26.860

It is way easier in something like awk:

$ echo 11 | awk 'function fib(n) {
    return n<2 ? n : fib(n-1) + fib(n-2)
} $1+0>0 {print fib($1)}'
89

$ echo 35 | awk 'function fib(n) {
    return n<2 ? n : fib(n-1) + fib(n-2)
} $1+0>0 {print fib($1)}'
9227465

Or, if you want comma separated digits:

$ echo 39 | awk 'function fib(n) {
    return n<2 ? n : fib(n-1) + fib(n-2)
} $1+0>0 {printf ("%'"'"'d\n", fib($1))}'
63,245,986

Shell Script to Generate Fibonacci Series

2 Answers2

Linked