是否存在斐波那契的迭代实现，这不是制表的

Question

我发现的所有迭代实现似乎一定是使用制表法。

动态编程是一种仅用于递归的替代方案，而它是迭代的强制解决方案？

Answer 1

fibonacci的迭代实现不使用制表，记忆或交换变量 - 此代码从我的答案中获得有关挂起学习功能样式的回答。

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, ...  ]

记住， procepure 与 Process - IE不同，递归过程可以产生迭代过程。下面，即使fibseq是递归定义的，它产生的过程是迭代 - 同样，没有制表，回忆或任何其他化妆条款

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

斐波那契数的定义是二项式系数的总和，它本身可以迭代地计算，作为1 s和 2 s的(n-1)所有组合物的表示。<</s。

在Haskell中，我们可以写：

-- 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