stepsFib3(1000)
結果
res33: BigInt = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
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) | |
} |
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段パターン |