7.2 Solution

Factorial is an interesting little function with a set of practical applications, one of them I explained here.

Factorial recursive implementation follows closely its mathematical definition (see below, where n! is a factorial of a number n).

\[ \begin{align*} n! = \left\{ \begin {aligned} & 1 \quad & \text{if } n = 1 \\ & n \times (n-1)! \quad & \text{otherwise} \end{aligned} \right. \end{align*} \]

Which can be translated into Julia’s:

function recFactorial(n::Int)::Int
    @assert 1 <= n <= 20 "n must be in range [1-20]"
    if n == 1
        return 1
    else
        return n * recFactorial(n-1)
    end
end

In general, factorial is well defined for positive integers and it grows very quickly (n > 20 would produce overflow, to resolve it we could use BigInt instead of Int) hence the @assert line. Next, for n equal 1 we return 1, otherwise we multiply n by recFactorial(n-1). Go ahead, follow the execution of the program for small inputs like recFactorial(3) in your head (similarly to recSum from Section 7.1).

To get you a better feel for recursion in Julia, here are two other equivalent implementations of recFactorial.

function recFactorialV2(n::Int)::Int
    @assert 1 <= n <= 20 "n must be in range [1-20]"
    return n == 1 ? 1 : n * recFactorialV2(n-1)
end

and

function recFactorialV3(n::Int, acc::Int=1)::Int
    @assert 1 <= n <= 20 "n must be in range [1-20]"
    return n == 1 ? acc : recFactorialV3(n-1, n * acc)
end

The second version (recFactorialV2) uses ternary operator instead of more verbose if else statements. The third version (recFactorialV3) relies on a so called accumulator (acc) that stores the result of a previous calculation (if any). recFactorialV3 is a tail-recursive function that is recommended in some programming languages, like Haskell and Scala, that can take advantage of this kind of code to produce (internally) effective function implementation.

Let’s go to the Fibonacci sequence. When I was a student, they said that dinners in the student’s canteen are like Figonacci numbers, i.e. each dinner is the sum of the two previous ones. To put it more mathematically, we get

\[ \begin{align*} fib(n) = \left\{ \begin {aligned} & 0 \quad & \text{if } n = 0 \\ & 1 \quad & \text{if } n = 1 \\ & fib(n-2) + fib(n-1) \quad & \text{otherwise} \end{aligned} \right. \end{align*} \]

Which expressed in Julia’s language give us:

function recFib(n::Int)::Int
    @assert 0 <= n <= 40 "n must be in range [0-40]"
    if n == 0
        return 0
    elseif n == 1
        return 1
    else
        return recFib(n - 2) + recFib(n - 1)
    end
end

recFib(10)

55

The numbers do not grow as fast as factorials, but the algorithm, although simple, is very inefficient. For instance, for recFib(3) I have to calculate recFib(1) + recFib(2), but recFib(2) will calculate recFib(1) inside of it as well. For greater numbers (inputs) the duplicated operations threaten to throttle the processor. On my laptop the computation for recFib(40) takes roughly 600-700 [ms], so more than half a second, a delay noticed even by a human.

Therefore we may improve our last function by using lookup tables/dictionaries like so:

function recFib!(n::Int, lookup::Dict{Int, Int})::Int
    @assert 0 <= n <= 40 "n must be in range [0-40]"
    if !haskey(lookup, n)
        lookup[n] = recFib!(n-2, lookup) + recFib!(n-1, lookup)
    end
    return lookup[n]
end

Notice that the function modifies lookup (hence ! appended to its name, per Julia’s convention). Inside we check if there is a value for a Fibonacci’s number in lookup. If not (!haskey(lookup, n)) then we calculate it using the known formula and insert it in lookup. Otherwise we just return the found value.

The last function (recFib!) is more performant, as:

fibs = Dict(0 => 0, 1 => 1)
recFib!(40, fibs)

102334155

takes only microseconds on its first execution (like a hundred times faster). Interestingly, running recFib!(40, fibs) for the second time reduces the time to nanoseconds (a million times faster) since there are no calculations performed the second time, just reading the number from the previously modified lookup). Run recFib(40) twice to convince yourself that it takes roughly the same amount of time every time it runs with the same n.