4.1 Recursion in Mathematics

There are countless examples of recursive functions. One of the simplest is the factorial function, defined mathematically as:

\[n!= \begin{cases} 1, & \text{if $n=0$}\\ n \cdot (n-1)!, & \text{otherwise} \end{cases}\]

The translation of this formula into Julia is straightforward:

factorial(n) = iszero(n) ? 1 : n*factorial(n-1)

It is important to notice that for all recursive functions there is at least:

• A base case (also called stopping condition), in which the result is immediately known;

• A recursive case, in which the original problem is reduced into a simpler sub-problem, closer to the base case.

If we analyze the factorial function, the base case is iszero(n), where the immediate result is 1, and the recursive case is n*factorial(n-1).

In general, a recursive function requires a conditional statement that detects the base case. Invoking a recursive function consists of successively solving simpler sub-problems until the simplest case of all (the base case) is reached, for which the result is immediate. This way, defining a recursive function tends to obey the following pattern:

1. Start by testing the base case;

2. Make a recursive call with a sub-problem increasingly closer to a base case;

3. Use the result of the recursive calls to produce the originally desired result.

Given this pattern, the most common errors associated with recursive functions are:

1. Not detecting the base case;

2. Recursive calls not reducing the complexity of the initial problem, i.e., not moving on to a simpler problem;

3. Not properly using the result of the recursive calls to produce the originally intended result.

Note that a recursive function that perfectly suites the cases for which it was created can be completely wrong for other cases. The factorial function is an example: when the argument is negative, the problem’s complexity increases, becoming further and further away from the base case:

factorial(-1)

\(\downarrow\)

-1*factorial(-2)

\(\downarrow\)

-1*(-2*factorial(-3))

\(\downarrow\)

-1*(-2*(-3*factorial(-4)))

\(\downarrow\)

-1*(-2*(-3*(-4*factorial(-5))))

\(\downarrow\)

-1*(-2*(-3*(-4*(-5*factorial(-6)))))

\(\downarrow\)

...

The most frequent error in a recursive function is never reaching the base case, either because the base case in not correctly detected, or because the recursion does not reduce the problem’s complexity. In this case, the number of recursive calls grows indefinitely until the computer’s memory is exhausted. At this point, the program generates an error message. In Julia’s case, this error is not entirely obvious because the evaluator only interrupts the evaluation, showing no results. Here is an example:

> factorial(3)

6

> factorial(-1)

ERROR: StackOverflowError:

Upon seeing such an error, we should verify whether the aforementioned recursion errors occur in the function in question.

4.1.1 Exercises 22

4.1.1.1 Question 59

The Ackermann function is set to non-negative numbers as follows: \[A(m, n) = \begin{cases} n+1 & \text{if $m = 0$} \\ A(m-1, 1) & \text{if $m > 0$ and $n = 0$} \\ A(m-1, A(m, n-1)) & \text{if $m > 0$ and $n > 0$}\end{cases}\] Define the Ackermann function in Julia.

4.1.1.2 Question 60