First, let's analyze how bad the performance is by revising the function to keep track of the number of executions. The code is as follows:

function fib(n)
    if n < 3
        return (result = 1, counter = 1)
    else
        result1, counter1 = fib(n - 1)
        result2, counter2 = fib(n - 2)
        return (result = result1 + result2, counter = 1 + counter1 + counter2)
    end
end

Every time the fib function is called, it keeps tracks a counter. If the value of n is smaller than 3, then it returns the count of 1 along with the result. If n is a larger number, then it aggregates the counts from the recursive calls to fib function.

Let's run it several times with various input values:

This simple example just illustrated how quickly it turns into a disaster when the computer has no memory about what it did before. A high school student would be able to calculate fib(20) manually with just 18 additions, discounting the first two numbers of the sequence. Our nice little function calls itself over 13,000 items!

Let's now put back the original code and benchmark the function. To illustrate the problem, I will start with fib(40):

For this task, the function should really return instantly. The 430 millisecond feels like an eternity in computer time!

We can use memoization to solve this problem. Here is our first attempt:

const fib_cache = Dict()

_fib(n) = n < 3 ? 1 : fib(n-1) + fib(n-2)

function fib(n)
    if haskey(fib_cache, n)
        return fib_cache[n]
    else
        value = _fib(n)
        fib_cache[n] = value
        return value
    end
end

First of all, we have created a dictionary object called fib_cache to store the results of previous calculations. Then, the core logic for the Fibonacci sequence is captured in this private function, _fib. 

The fib function works by first looking up the input argument from the fib_cache dictionary. If the value is found, it returns the value. Otherwise, it invokes the private function, _fib, and updates the cache before returning the value.

The performance should be much better now. Let's test it quickly:

We should be must happier with the performance result by now.