4 Recursion
Imagine we already have a function that computes the square of a number and we want to define the function that computes the cube of a number. We can easily do it by combining the square function with an additional multiplication, i.e.:
cube(x) = square(x)*x
Similarly, we can define the function fourth_power in terms of the cube function and one additional multiplication:
fourth_power(x) = cube(x)*x
Obviously, we can continue to define new functions to compute larger powers, but this is not a practical method. It would be much more useful if we could generalize this process by simply defining the exponentiation function that, from two numbers (base and exponent) computes the first one raised to the power of the second one.
The definitions of the cube and the fourth_power functions give us an important clue: in order to compute a power we only need the preceding power and one additional multiplication.
In other words, we have:
power(x, n) = preceding_power(x, n)*x
Although we were able to generalize our power calculation problem, there is still one unanswered question: how can we calculate the preceding power? The answer will be: the preceding power of \(n\) is the power of \(n-1\). This means that preceding_power(x, n) is exactly the same as power(x, n-1). Based on this idea, we can rewrite the previous definition:
power(x, n) = power(x, n-1)*x
Unfortunately, our solution has a problem: regardless of the exponentiation we try to compute, we will never be able to get the final result. In order to understand this problem, consider the following example: \(4\) raised to the third power, i.e., power(4, 3).
According to the power function definition, we will have the following sequence of evaluations:
power(4, 3)\(\downarrow\)power(4, 2)*4\(\downarrow\)(power(4, 1)*4)*4\(\downarrow\)((power(4, 0)*4)*4)*4\(\downarrow\)(((power(4, -1)*4)*4)*4)*4\(\downarrow\)((((power(4, -2)*4)*4)*4)*4)*4\(\downarrow\)(((((power(4, -3)*4)*4)*4)*4)*4)*4
It becomes clear that this process will never finish. This is due to the fact that we have not said when to stop the process of successively calculating \(x\) raised to the power of \(n-1\).
We saw that when the exponent is \(2\), the square function returns the correct answer, so reaching the case \(n = 2\) would allow us to stop the process. However, it is possible to have an even simpler case: when the exponent is \(1\), the result is the value of the base. Finally, the simplest case of all is when the exponent is \(0\), being the result always \(1\), regardless of the base value. This last case is easy to understand when we see that the evaluation of power(4, 2) (i.e., the square of four) is reduced to power(4, 0)*4*4. For this expression to be equal to 4*4, it is necessary that the evaluation of power(4, 0) produces 1.
We are now capable of defining the power function correctly:
When the exponent is \(0\), the result is \(1\);
Otherwise, we calculate the base raised to the power of the preceding exponent and we multiply it to the base:
power(x, n) = iszero(n) ? 1 : power(x, n-1)*x
The previous example is an example of a recursive function, i.e., a function that is defined in terms of itself. In other words, a recursive function is a function that calls itself inside its own definition. This use is obvious when we unwrap the evaluation process of power(4, 3):
power(4, 3)\(\downarrow\)power(4, 2)*4\(\downarrow\)(power(4, 1)*4)*4\(\downarrow\)((power(4, 0)*4)*4)*4\(\downarrow\)((1*4)*4)*4\(\downarrow\)(4*4)*4\(\downarrow\)16*4\(\downarrow\)64
Recursion is the mechanism that allows a function to call itself during its own evaluation process. Recursion is one of the most important programming techniques since, in fact, many apparently complex problems have surprisingly simple recursive solutions.