DEV Community

loading...

Discussion on: Making recursions faster, 7 million times...

Collapse
juancarlospaco profile image
Juan Carlos

Theres a big bug there!, you need 2 "start" variables, otherwise the time is wrong.

Heres my Nim solution:

import times

var fibo_cache = newSeq[int](200)

func recursive_fibonacci(num: int): int =
  if num in {0, 1}: return num
  result = recursive_fibonacci(num - 1) + recursive_fibonacci(num - 2)

proc dynamic_fibonacci(num: int): int =
  if num in {0, 1}: return num
  elif 0 != fibo_cache[num]: return fibo_cache[num]
  fibo_cache[num] = dynamic_fibonacci(num - 1) + dynamic_fibonacci(num - 2)
  result = fibo_cache[num]

when isMainModule:
  const fibo_num = 45  # change as needed
  let start = now()
  echo "Dynamic fibonacci answer = ", dynamic_fibonacci(fibo_num)
  echo "Time for Dynamic = ", now() - start
  let start2 = now()
  echo "Recursive fibonacci answer = ", recursive_fibonacci(fibo_num)
  echo "Time for Recursive = ", now() - start2
Enter fullscreen mode Exit fullscreen mode

I use let start2 = now() to fix the bug.

Also dynamic_fibonacci() has Side-Effects but recursive_fibonacci() does not.

Collapse
reclusivecoder profile image
Manish Author

Fixed, thanks :-)