Recursive Fibonacci in Bash script

Question

This is my attempt:

#!/bin/bash

function fibonacci(){

first=$1
second=$2

if (( first <= second ))
then
return 1

else 

return $(fibonacci $((first-1)) ) + $(fibonacci $((second-2)) )
fi
}

echo $(fibonacci 2 0)

I think i'm having trouble with the else statement. I get the error return: +: numeric argument required on line 14.

The other problem that i'm having is that the script doesn't display any numbers even if i do echo $(fibonacci 0 2). I thought it would display a 1 since i'm returning a 1 in that case. Can someone give me a couple of tips on how to accomplish this?

After checking out some of your answers this is my second attempt.. It works correctly except that it displays the nth fibonacci number in the form 1+1+1+1 etc. Any ideas why?

#!/bin/bash

function fibonacci(){

first=$1
second=$2

if (( first <= second ))
then
echo 1


else 

echo $(fibonacci $((first-1)) ) + $(fibonacci $((first-2)) )
fi
}

val=$(fibonacci 3 0)
echo $val

My final attempt:

#!/bin/bash

function fibonacci(){

first=$1

if (( first <= 0 ))
then
echo 1


else 

echo $(( $(fibonacci $((first-1)) ) + $(fibonacci $((first-2)) ) ))
fi
}

val=$(fibonacci 5)
echo $val

thanks dudes.

Answer 1

Short version, recursive

fib(){(($1<2))&&echo $1||echo $(($(fib $(($1-1)))+$(fib $(($1-2)))));}

Answer 2

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.

Answer 3

While calculating fibonacci numbers with recursion is certainly possible, it has a terrible performance. A real bad example of the use of recursion: For every (sub) fibonacci number, two more fibonacci numbers must be calculated.

A much faster, and simple approach uses iteration, as can be found here:

https://stackoverflow.com/a/56136909/1516636

Answer 4

The $(...) substitution operator is replaced with the output of the command. Your function doesn't produce any output, so $(...) is the empty string.

Return values of a function go into $? just like exit codes of an external command.

So you need to either produce some output (make the function echo its result instead of returning it) or use $? after each call to get the value. I'd pick the echo.

Answer 5

#!/bin/bash

function fib(){
    if [ $1 -le 0 ]; then
        echo 0
    elif [ $1 -eq 1 ]; then
        echo 1
    else
        echo $[`fib $[$1-2]` + `fib $[$1 - 1]` ]
    fi

}

fib $1