Print Fibonacci series using recursion in bash with only 1 variable

Question

I'd like to know how to print Fibonacci series using recursion in bash with only 1 variable.

From what I've done:

fib()
    {
    i=$1
    if (( $i <= 1 ))
    then echo 0
    elif (( $i == 2 ))
    then echo 1
    else

    echo $(( $(fib $(($i - 1)) ) + $(fib $(($i - 2)) ) ))

fi
 }

echo $(fib $1)

I get the correct output of the final iteration, for example if I enter 10 I will get 34, but I'd like to print the whole sequence of numbers, i.e. all the iterations as well. How can I achieve that?

Another way I tried was by:

#!/bin/bash
arr[0]=0
arr[1]=1

for (( i=0; i<=10; i++ ))
do
    echo -n "${arr[0]} "
    arr[0]=$((${arr[0]} + ${arr[1]} ))
    arr[1]=$((${arr[0]} - ${arr[1]} ))
done
echo ""

But obviously here I've used a for loop, but I don't want to use another variable.

Answer 1

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.

Answer 2

Variables in bash are global by default. You need to make i local explicitly.

 fib () {
     local i
     i=$1
     if (( i <= 1 )); then
         echo $i
     else
         echo $(( $(fib $((i-1)) ) + $(fib $((i - 2)) ) ))
     fi
}

(Also, your base cases are a little off if you are starting with 0, and 2 need not be a base case; fib 2 can be derived from the base cases fib 0 and fib 1.)

Answer 3

If you want to print each fibonacci value from 1 to $n, I suggest:

fib_r() {
    local i=$1
    if (( i < 0 )); then
        echo "Error: negative numbers not allowed" >&2
        exit 1

    elif (( i <= 1 )); then
        echo $i

    else
        echo $(( $($FUNCNAME $((i - 1)) ) + $($FUNCNAME $((i - 2)) ) ))
    fi
}

fib() {
    local i
    for (( i = 1; i <= $1; i++ )); do
        fib_r $i
    done
}

fib 10

outputs

0
1
1
2
3
5
8
13
21
34

It's still one variable, albeit one per function.

I use the bash variable $FUNCNAME in the recursive function so you don't have to hardcode the function name within itself. I got bit by not updating that line when I renamed the function.

---

Of course your performance will greatly improve if you cache the results: "fib 16" takes, on my VM, about 3.5 sec without caching and about 0.03 sec with caching.

fib_r() {
    local i=$1
    if (( i < 0 )); then
        echo "Error: negative numbers not allowed" >&2
        exit 1

    elif [[ -n ${fib_cache[i]} ]]; then
        echo "${fib_cache[i]}"

    elif (( i <= 1 )); then
        echo $i

    else
        echo $(( $( $FUNCNAME $((i - 1)) ) + $( $FUNCNAME $((i - 2)) ) ))
    fi
}

fib_cache=()

fib() {
    local i
    for ((i=1; i<=$1; i++)); do
        fib_cache[i]=$(fib_r $i)
        echo "${fib_cache[i]}"
    done
}