result.md

stepsFib3(1000)

結果

res33: BigInt = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

stepsFib.scala

import annotation.tailrec
def stepsFib3(n: BigInt): BigInt = {
  val One = BigInt(1)
  @tailrec
  def tailrecFib(n: BigInt, next: BigInt, res: BigInt): BigInt = n match {
    case One => res
    case _ =>
      tailrecFib(n - 1, next + res, next)
  }
  tailrecFib(n, 2, 1)
}

例示&一般化.txt

1段 0から1段上る場合の1通り = 1
2段 0->2, 0->1->1 = 1 + 1 = 2
3段 0->1->3, 0->2->3, 0->1->2->3 = 3
4段 0->1->2->3->4, 0->1->2->4, 0->1->3->4, 0->2->3->4, 0->2->4, = 5
以降、n段目 = n-1段目から1段登る場合と、n-2段目から2段登る場合 = n-1段のパターン+n-2段パターン