Fibonacci & for loop: how are the commands executed step by step?

user_14642966 0
Viewed 82
#!/bin/bash
a=0
b=1
echo "give a number:"
read n
clear
echo "the fibonacci sequence until $n:"
for (( i=0; i<n; i++ ))
do
  echo -n "$a "
  c=$((a + b))
  a=$b
  b=$c
done

If I interpret it well, this code echoes a $a value after every i++ jumps, then switches the variables as you can see, then on the next i++ loop jump it happens again until "i" reaches "n".

Question: if we want in every loop jump the value of the new "c" why shall we echo $a? I see the connection that: a=$b, b=$c, and c=$((a + b)) but i don't get it why do we refer to $a when doing echo?

Is there a more elegant solution?

fibonacci bash
1 Answers

You mean, “never ever calculate anything needlessly, ever”? It is possible, of course, but it depends on how much ugliness in the control logic you are willing to tolerate. In the example below, fibonacci1 calculates at most one extra element of the series that may not get printed out and fibonacci2 never calculates any extra series elements and everything makes it to the standard output.

Is any of that “elegant”? Probably not. This is actually a common problem most people encounter when coding (in languages other than purely functional ones): Most high(er)-level languages (unlike e.g. assemblers) provide predefined control structures that work great in typical and obvious cases (e.g. one control variable and one operation per iteration) but may become “suboptimal” in more complex scenarios.

A notoriously common example is a variable that stores a value from the previous iteration. Let’s assume you assign it at the very end of the loop. That works fine, but… Could you avoid the very last assignment (because it is useless), instead of leaving it to the compiler’s wisdom? Yes, you could, but then (e.g.) for ((init; condition; step)); do ...; ((previous = current)); done becomes (e.g.) for ((init;;)); do ...; ((step)); ((condition)) || break; ((previous = current)); done.

On one hand, a tiny bit of something (such as thin air) may have been “saved”. On the other hand, the code became assembler-like and harder to write, read and maintain.

To find a balance there^^^ and {not,} optimize when it {doesn’t,does} matter is a lifelong struggle. It may be something like CDO, which is like OCD, but sorted correctly.

fibonacci1() {
  local -ai fib=(0 1)
  local -i i
  for ((i = $1; i > 2; i -= 2)) {
    printf '%d %d ' "${fib[@]}"
    fib=($((fib[0] + fib[1])) $((fib[0] + 2 * fib[1])))
  }
  echo "${fib[@]::i}"
}

fibonacci2() {
  trap 'trap - return; echo' return
  local -i a=0 b=1 i="$1"
  ((i)) || return 0
  printf '%d' "$a"
  ((--i)) || return 0
  printf ' %d' "$b"
  for ((;;)); do
    ((--i)) || return 0
    printf ' %d' "$((a += b))"
    ((--i)) || return 0
    printf ' %d' "$((b += a))"
  done
}

for ((i = 0; i <= 30; ++i)); do
  for fibonacci in fibonacci{1,2}; do
    echo -n "${fibonacci}(${i}): "
    "$fibonacci" "$i"
  done
done
user_85849290
Related