Languages with hash-tables can support an extremely useful form of optimization called memoization. Memoized functions reduce the number or frequency of function calls by caching the results of previous calls, and the best way to store these results is in a hash-table. This can very dramatically speed up a program that must make very many calls to the same function, and the efficiency of the memoized function increases as the cache grows.

;; lisp again....
(defvar *facttable* (make-hash-table :test 'equal))
(setf (gethash 3 *facttable*) 6)
(defun factl (n)
"Memoized factorial function"
 (cond ((= n 0) 1)
        ((equal (gethash n *facttable*) nil) 
          (let* ((x (* n (factl (- n 1))))) 
           (setf (gethash n *facttable*) x) x))
        (t (gethash n *facttable*))
  )
 )

You are sacrificing space for speed, since hash-table lookups are faster than some calculations. Recursive functions, especially deep recursions, benefit most from memoization. Here is an example run on a raspberry pi 2B, not a fast computer

(defun fib(n)
"Fibonacci sequence"
 (cond
     ((< n 2) 1)
     ( t (+ (fib (- n 1)) (fib (- n 2))))
  )
 )

(time (fib 35))
real time : 4.183 secs       ; Over 4 seconds!
run time  : 4.179 secs
gc count  : 68 times
consed    : 955544688 bytes
14930352                     ; 35^th Fibonacci number

You probably think that we are talking small potatoes here, how much faster can a memoized function be?

(defparameter *fibm* (make-hash-table :test 'equal))
(defun fibm(n) 
"Memoized Fibonacci sequence"
(cond
     ((< n 2) 1)
     ((equal (gethash n *fibm*) nil)
     (let* ((x (+ (fibm (- n 1)) (fibm (- n 2))))) 
           (setf (gethash n *fibm*) x) x)) ; add to table, return x
           (t (gethash n *fibm*))))

(time (fibm 200))
real time : 0.000 secs    ; so fast it does not register
run time  : 0.000 secs
gc count  : 1 times
consed    : 21552 bytes
453973694165307953197296969697410619233826

Now you see why we used lisp, would be beyond the ability of other programming languages without the use of a multiple precision library. On the R-pi took (fibm 20000) less than seconds.
I want to stress that we used the same algorithm in both functions

In the un-memoized version, a very large tree of redundant calculations is performed.
To compute we branch and find and . To compute we must compute and , so right away you see we are computing twice. In the memoized, there are no redundant calculations. Once is computed it is stored and looked up if needed rather than re-calculated.

We did everything by hand in the lisp example, let’s try this in julia, using the Memoize library package.

using Memoize
@memoize function ufib(n)
n < 2 ? 1 : ufib(n-1) + ufib(n-2)
end
@time ufib(35)
# 0.000006 seconds
# 14930352
# pretty fast, not lisp-fast but fast
@time ufib(200)
# 0.000167 seconds (991 allocations: 37.812 KiB)
# 3721511182311577122,  clearly wrong, the largest integer julia supports is
typemax(Int64)
9223372036854775807

What happened? Julia has no native support for integers larger than Int64, so it just checks out without any warning or indication that it is doing so. Using BigInt or big”100″ are any other arbitrary precision trick fails. Julia changes more rapidly than its documentation can keep up with, so perhaps this issue will be resolved in the near future.