What is purpose of this? Optimize a function which uses a terrible algorithm? Why not use a good algorithm? In Racket for instance

(define (memoize/1 f)
  (define h (make-hasheqv))
  (λ (a)
    (hash-ref! h a (thunk (f a)))))

(define fib
  (memoize/1
   (λ (x)
     (if (< x 2) 
         1
         (+ (fib (- x 2)) 
            (fib (- x 1)))))))

And now

> (time (fib 39))
cpu time: 0 real time: 0 gc time: 0
102334155
> (time (fib 50000))
cpu time: 77 real time: 88 gc time: 29
174387413787277868303885543...

(10,000 digit number, results are from cold Racket so memo table was empty initially.)

Is entertaining then to try to compute say (log (fib 500000) 10). Bignums tend to get pretty slow then.