7.1 Problem

Recursion is a programming technique where a function invokes itself in order to solve a problem. It relies on two simple principles:

1. know when to stop
2. split the problem into a single step and a smaller problem

And that’s it. Let’s see how this works in practice.

For that we’ll write a recursive function that sums the elements of a vector of integers.

function recSum(v::Vec{Int})::Int
    if isempty(v)
        return 0
    else
        return v[1] + recSum(v[2:end])
    end
end

We begin by defining our edge case (know when to stop). If the vector (v) is empty (if isempty(v)) we return 0 (BTW. Notice that zero is a neutral mathematical operation for addition, any number plus zero is just itself). Otherwise (else) we add the first element of the vector (v[1], single step) to whatever number is returned by recSum with the rest of the vector (v[2:end]) as an argument (smaller problem).

Time for a couple of examples.

For

recSum([1])

1

the execution of the program looks something like

recSum([1]) # triggers else branch
    1 + recSum([]) # triggers if branch (stop)
        1 + 0 # stop reached, time to return
1

Whereas for

recSum([1, 2, 3])

6

we get

recSum([1, 2, 3]) # triggers else branch
    1 + recSum([2, 3]) # triggers else branch
        1 + 2 + recSum([3]) # triggers else branch
            1 + 2 + 3 + recSum([]) # triggers if branch (stop)
                1 + 2 + 3 + 0 # stop reached, time to return
6

Although difficult to imagine recSum works equally well for a bit broader range of numbers.

1:100 |> collect |> recSum

5050

Believe it or not, but that last one you can calculate fairly easily yourself if you apply the Gauss method.

Anyway, usually recursion is not very effective and it can be rewritten with loops. Moreover, too big input, e.g. 1:100_000, will likely cause an error with recSum, but not with built-in sum. Still, for some problems recursion is an easy to implement and elegant solution that gets the job done. Therefore, it is worth to have this technique in your programming toolbox.

Classical examples of recursive process in action are factorial and Fibonacci sequence. For this task your job is to implement the functions to calculate both the numbers.