narski

  # fib for basic b's
  def fib(n):
    ## Base case
    if n == 0 or n == 1:
      return n
    
    return fib(n-1) + fib(n-2)

  # optimize-pilled memoize-chad version
  def fib(n, saved={}):
    if n in saved:
      return saved[n]
    
    if n == 0 or n == 1:
      saved[n] = n
    else:
      saved[n] = fib(n-1) + fib(n-2)
    
    return saved[n]

  |=  n=@ud
  ?:  (lte n 1)
    n
  %+  add
    $(n (dec n))
  $(n (sub n 2))

  :-  %say
  |=  [* [n=@ud ~] [cache=(map @ud @ud) ~]]
  :-  %noun
  ^-  [sum=@ud cache=(map @ud @ud)]
  =/  has-n  (~(get by cache) n)
  ?~  has-n
    ?:  (lte n 1)
      [n (~(put by cache) n n)]
    =/  minus-1  $(n (dec n))
    =/  minus-2 
      =/  search  (~(get by cache.minus-1) (sub n 2))
      ?~  search  0
      (need search)
    :-  (add sum.minus-1 minus-2)
    (~(put by cache.minus-1) n (add sum.minus-1 minus-2))
  [(need has-n) cache]

  > =fib-8 +fib 8
  > sum.fib-8
  21

  > =old now
  > =res +fib 18
  > sum.res
  2.584
  > (sub now old)
  1.688.849.860.263.936
  :: now with the non-memoized code...
  > =before now
  > +fib 18
  2.584
  > (sub now before)
  1.125.899.906.842.624