Recursive Fibonacci function in Bash

Or why you better not use recursion is Bash

First, the loop version:

function fib() {
    declare -l cur=0 next=1 final=$(($1-1)) tcur

    for ((i=0; i<final; i++)); do
        tcur=$cur
        cur=$next
        next=$((tcur+next))
    done
    rval=$cur
}

And now the recursive version. I've added caching of previously calculated values to help with performance:

unset fib_cache; declare -ia fib_cache
function fib() {
    declare -li n=$1 n_1 n_2 l

    l=${#fib_cache[*]}
    if ((n<=l)); then
        rval=${fib_cache[$n]}
        return
    fi

    if ((n<3)); then
        rval=$((n-1))
        fib_cache[$n]=$rval
        return
    fi

    fib $((n-2))
    n_2=$rval
    fib $((n-1))
    n_1=$rval

    rval=$((n_2 + n_1))
    fib_cache[$n]=$rval
    return
}

Performance

Lets test how fast Bash can crunk Fibonacci on my laptop. Here is the test script:

for i in $(seq 1000); do
    unset fib_cache; declare -ia fib_cache
    fib 93
done

I've used fib 93 - its a max Fibonacci sequence number you can store in Bash arithmetic variable before getting overflow.

I've run it 10 times and measured average time:

• Loop version: Runs 1.19 seconds on average. I.e. it takes 1.19 seconds to calculate fib 93 thousand  times. How fast is that? Well, similar C code, compiled with -O3 runs this task in 0.0001 seconds. About 10,000 faster
• Recursion version: Runs 10.41 seconds on average. Times 10 slower. And this is with cache. Without cache it did not complete in 15 minutes and I gave up

Conclusion

Think twice before considering recursive functions in Bash.