フィボナッチ数列を漸化式と繰り返しを使って。Fibonacci with Recursion and Interation

フィボナッチ数列の求め方と言えば、再帰で書くのが一番最初に思いつく方法かもしれません。けど、再帰を使用すると数が大きくなるに連れて無駄な計算量が増えていき、計算に時間がかかります。そこで、無駄な計算数を避けるためにメモ化が出てきました。 しかし再帰を使用すると基本的に計算スピードがループ処理よりも遅くなる印象があります。実際どの程度遅くなるかは調べてませんが。今度調べて見たいと思います。 ということで、ループを使ってフィボナッチ数列も求めることができるのでしょうか？はいできます。 こんな感じになります。

const fibonacci = (len) => {
  let first = 1, second = 1;
  for (let i = 1; i < len - 1; i++) {
    current = first + second;
    first = second;
    second = current;
  }
  return current;
}

さらに遊び心を出して、各桁の数字を足して、その数字で元の数字が割り切れる数字を7個見つけ出すことにして見たのが以下です。

const fibonacci = (len) => {
  let first = 1, second = 1, count = 0; const result = [];
  for (let i = 1; i < len - 1; i++) {
    if (`${second}`.length > 3 && count < 7 && second % `${second}`.split("").reduce((total, crr) => total + parseInt(crr), 0) === 0) {
      result.push(second)
      count++;
    }
    current = first + second;
    first = second;
    second = current;
  }
  return result;
}

これに1345を代入してみると

console.log(fibonacci(1345));

[ 2584,
  14930352,
  86267571272,
  498454011879264,
  679891637638612200,
  31940434634990100000,
  218922995834555200000 ]

結構いかつい数字が並んでいます。 今日はここまでです。 ちなみに再帰って英語でrecursion, recursionは日本語で漸化式というそうです。再帰と漸化式って同じ意味合いとのことです。大学で漸化式バリバリ使ってましたけど、再帰と同じことしてるとは知りませんでした。新しい発見です。