What's wrong with my variable assignment?

Question

I'm trying to code a fibonacci function that takes an input int as length of sequence. Here's my code:

function fib {
        local len=$1
        echo "len = $len"

        local arr=(0 1 1)

        if [[ $len -le 3 ]]
        then
                echo ${arr[@]:0:$len}
                let arr=${arr[@]:0:$len}
                echo $arr
        else
                while [[ ${#arr[*]} -lt $len ]]
                do
                        local sum=${arr[${#arr[*]}]}+${arr[${#arr[*]}-1]}
                        let arr+=$sum
                        echo "curren len = ${#arr[*]}"
                done
        fi

        echo "arr = $arr"
}

And here's what I get when I call the function:

 fib 2
len = 2
0 1
0
arr = 0
 fib 3
len = 3
0 1 1
0
arr = 0

Please ignore if it's efficient for now. Why is it i get the right sequence when simply echoing? But not when I let arr=?

Answer 1

You need to read through the long and boring chapter on expansions in man bash, which shows how arrays are used. "${array[@]}" expands an array’s values as separate tokens. "${!array[@]}" expands an array’s indices (or keys) as separate tokens. Using * instead of @ produces a single string, delimited by the first character from $IFS. Expanding an array variable as a scalar ("$array") yields "${array[0]}", which may or may not exist, because indexed arrays are sparse and may not contain a [0] element and associative arrays may or may not contain a ['0'] key. The snippet below also shows the nice “debugging” expansions provided by Bash. (Look for @A.)

generate_fibonacci_sequence() {
  local -i counter="$1"
  local -n _output_array="$2"  # declare -ai
  _output_array=()
  ((counter)) || return 0
  local -i a=0 b=1
  for ((;;)); do
    _output_array+=(a)
    ((--counter)) || return 0
    ((b += a))
    _output_array+=(b)
    ((--counter)) || return 0
    ((a += b))
  done
}

declare -ai sequence

for length in {0..20}; do
  generate_fibonacci_sequence "$length" 'sequence'
  printf '%s\n%s %s %s\n' "${length@A}" "${sequence[@]@A}"
  printf '['
  for i in "${!sequence[@]}"; do
    printf '(%d:%d)' "$i" "${sequence[i]}"
  done
  printf ']\n\n'
done

Beginning of the output:

length='0'
declare -ai sequence=()
[]

length='1'
declare -ai sequence=([0]="0")
[(0:0)]

length='2'
declare -ai sequence=([0]="0" [1]="1")
[(0:0)(1:1)]

length='3'
declare -ai sequence=([0]="0" [1]="1" [2]="1")
[(0:0)(1:1)(2:1)]

length='4'
declare -ai sequence=([0]="0" [1]="1" [2]="1" [3]="2")
[(0:0)(1:1)(2:1)(3:2)]

length='5'
declare -ai sequence=([0]="0" [1]="1" [2]="1" [3]="2" [4]="3")
[(0:0)(1:1)(2:1)(3:2)(4:3)]

length='6'
declare -ai sequence=([0]="0" [1]="1" [2]="1" [3]="2" [4]="3" [5]="5")
[(0:0)(1:1)(2:1)(3:2)(4:3)(5:5)]

length='7'
declare -ai sequence=([0]="0" [1]="1" [2]="1" [3]="2" [4]="3" [5]="5" [6]="8")
[(0:0)(1:1)(2:1)(3:2)(4:3)(5:5)(6:8)]

...

In any case, note that Bash uses signed 64-bit integers under the hood, with underflow / overflow behaviors that would be considered undefined in (e.g.) C++:

$ echo $((2**63))
-9223372036854775808
$ echo $((2**63 - 1))
9223372036854775807

With that said, it may be better to calculate large Fibonacci numbers in Python, which uses GNU MP under the hood. (Or use GNU MP directly.)