CODEWITHSUNDEEP
bashrecursion
wegmans
wegmans

Reputation: 13

Trying to call a function within a function in Bash but it returns errors

I had looked on overflow and exchange, but I can't seem to find an answer for this. I am currently trying to make a recursive fibonacci function. However when I try to test it (using command line entry) it keeps returning the error

fork: retry: Resource temporarily unavailable

I had found a post saying it had to do with shell resource limits, but I felt like that probably wasn't my issue since I've seen separate posts with recursive functions being able to call their function fine enough.

I had broken up the operation into parts to see what exactly was happening, but I can't find a specific problem - it may have to do with how i'm calling my function, but I'm not sure, either.

I can pass the parameter I want just fine, though. It just prints the same error for whatever number I put in. If I enter 5, it echoes the fork error five times. It returns, but doesn't return the values...

For specification, I currently use Bash Version 4.4.20(1)

function fib_r
{
    int=$1

    for ((i=1; i<=int; i++))
    do

    f1=$(fib_r $((int-1)))
    f2=$(fib_r $((int-2)))
    fibo=$((f1+f2))

    done
}

What I want to achieve is when you enter a number on command line, It does calculate that number, however it shows the calculated number at each step, rather than return the final value from start to end:

An example output:

1          1
2          1
3          2
4          3
5          5
6          8
7          13
8          21
9          34
10         55

Upvotes: 1

Views: 105

Answers (1)

pjh
pjh

Reputation: 8064

This Shellcheck-clean code fixes a few problems with the code in the question:

function fib_r
{
    local -r n=$1

    if (( n == 0 )); then
        echo 0
    elif (( n == 1 )); then
        echo 1
    else
        local -r f1=$(fib_r "$((n-1))")
        local -r f2=$(fib_r "$((n-2))")
        echo "$((f1+f2))"
    fi

    return 0
}
  • It adds code for base cases (0 and 1) to stop the recursion. The original code had no base cases so the recursion continued until resources were exhausted.
  • The function echos the result so it is available to the caller. Command substitution ($(command)) is usually only useful if the command prints its result(s) to standard output.
  • The loop was removed because this is supposed to be a recursive function (and the loop wasn't useful).
  • local is used to make variables local to the function so they won't clash with variables used elsewhere in a program that uses the function. The -r (readonly) option is used because the variables never need to be changed within the function and it prevents them being accidentally changed by other functions.
  • The variable name int was changed to n because that is more conventional for functions like this (and int seems really strange to people who know C, or related programming languages).

Note that this function is very slow. That is partly because it uses command substitution (which runs an expensive sub-process every time) to return results, but mostly because this particular recursive algorithm is very inefficient (exponential complexity, see Computational complexity of Fibonacci Sequence). Much faster recursive implementations are possible.

The question was updated to request a function that prints all of the Fibonacci numbers up to a given number. This is a recursive function that does that:

function fib_r
{
    local -r n=$1
    local -r depth=${2-1}
    local -r f1=${3-1}
    local -r f2=${4-0}

    if (( depth <= n )); then
        printf '%2d  %d\n' "$depth" "$f1"
        fib_r "$n" "$((depth+1))" "$((f1+f2))" "$f1"
    fi

    return 0
}

This uses a much more efficient algorithm (O(n)), so it can calculate all of the Fibonacci numbers that can be represented by a 64-bit integer in a fraction of a second. Run fib_r 92 to do that.

Upvotes: 2

Related Questions