Skip to main content
oops
Source Link
glenn jackman
  • 248.6k
  • 42
  • 233
  • 362

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 1$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 1$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
}

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 1

    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 1

    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
}

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
}
Source Link
glenn jackman
  • 248.6k
  • 42
  • 233
  • 362

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 1

    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 1

    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
}