Advertisement
MiroJoseph

Memoized Fibonacci

Apr 14th, 2020
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Scala 0.51 KB | None | 0 0
  1. My:
  2. object Sol {
  3. def fib(n: Int): BigInt = {
  4.   @annotation.tailrec
  5.   def getTailRec(index: Int, prev: BigInt, current: BigInt): BigInt = {
  6.     if (index <= 0) {
  7.       current
  8.     } else {
  9.       getTailRec(index - 1, prev = prev + current, current = prev)
  10.     }
  11.   }
  12.   getTailRec(n, prev = 1, current = 0)
  13. }
  14. }
  15.  
  16. Other:
  17. import scala.collection.mutable.Map
  18. object Sol {
  19.   val cached: Map[Int, BigInt] = Map(0 -> 0, 1 -> 1)
  20.   def fib(n: Int): BigInt =
  21.     cached.getOrElseUpdate(n, fib(n-1) + fib(n-2))
  22. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement