CODEWITHSUNDEEP
bashfibonacci
rage
rage

Reputation: 1837

Recursive Fibonacci in Bash script

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.

Upvotes: 1

Views: 9593

Answers (6)

vanyabeat
vanyabeat

Reputation: 1

This is correct for recursive solution

#!/bin/bash

function fib() {
    if [[ $1 == 0 ]]; then
        echo 0
    elif [[ $1 == 1 ]]; then
        echo 1
    else
        echo $(( $(fib "$(( $1-1 ))") + $(fib "$(( $1-2 ))") ))
    fi
}

#calc first 32 numbers in fib-ci sequence

for item in {1..32}
do
    echo $(fib $item)
done

Upvotes: 0

Floyd
Floyd

Reputation: 789

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

Upvotes: 0

niry
niry

Reputation: 3308

Short version, recursive

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

Upvotes: 0

Andrii Kovalchuk
Andrii Kovalchuk

Reputation: 4897

#!/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

Upvotes: 5

Jester
Jester

Reputation: 58772

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.

Upvotes: 1

user2404501
user2404501

Reputation:

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.

Upvotes: 2

Related Questions