Does there exist an iterative implementation of fibonacci that is not a tabulation?

Question

All the iterative implementations that I have found seem to necessarily be using a tabulation method.

Is dynamic programming an alternative only to recursion, while it is a mandatory solution for iteration?

Answer 1

An iterative implementation of fibonacci that does not use tabulation, memoization, or a swap variable – this code from my answer here on getting hung-up learning functional style.

const append = (xs, x) =>
  xs.concat ([x])

const fibseq = n => {
  let seq = []
  let a = 0
  let b = 1
  while (n >= 0) {
    n = n - 1
    seq = append (seq, a)
    a = a + b
    b = a - b
  }
  return seq
}

console.log (fibseq (500))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...  ]

And remember, procedure differs from process – ie, recursive procedures can spawn iterative processes. Below, even though fibseq is defined recursively, the process that it spawns is iterative – again, no tabulation, memoization, or any other made-up terms going on

const recur = (...values) =>
  ({ type: recur, values })

const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }
      
const fibseq = x =>
  loop ((n = x, seq = [], a = 0, b = 1) =>
    n === 0
      ? seq.concat ([a])
      : recur (n - 1, seq.concat ([a]), a + b, a))

console.time ('loop/recur')
console.log (fibseq (500))
console.timeEnd ('loop/recur')

// [ 0,
//   1,
//   1,
//   2,
//   3,
//   5,
//   8,
//   13,
//   21,
//   34,
//   ... 490 more items ]
// loop/recur: 5ms

Answer 2

There is a definition of Fibonacci numbers as a sum of binomial coefficients, which themselves can be calculated iteratively, as a representation of all the compositions of (n-1) from 1s and 2s.

In Haskell, we could write:

-- https://rosettacode.org/wiki/Evaluate_binomial_coefficients#Haskell
Prelude> choose n k = product [k+1..n] `div` product [1..n-k]

Prelude> fib n = sum [(n-k-1) `choose` k | k <- [0..(n-1) `div` 2]]

Prelude> fib 100
354224848179261915075