Recursive Functions
Contents
Recursive Functions¶
When designing algorithms, one of the most basic design patterns is the function. A function encapsulates a task. This allows us to study one specific task, then use it inside larger programs. For example, we might encrypt data before sending it over a network. There are lots of tasks that require encryption, so if we can design one encryption algorithm, then implement it as a function. The function can then be used in many places.
A function has three parts:
The function name is the name we use to refer to the function.
The function parameters are placeholder variables for the values the function needs to do its job.
The function return value is the result of the computation.
We will write a function to compute the remainder of a division. In mathematics, this is traditionally written as the \(a \mod b\). We want to compute \( a \mod b = r\) or \(a\%b=r\). This requires us two know two values \(a\) and \(b\). We then compute one value \(r\).
Imagine we were coding in a language that had division but not remainder. The divide command computes the quotient of division \(a / b = q\). The remainder is whatever is left. For example, \(9 / 2 = 4\). The quotient of this division is 4. If we compute \(2 * 4 = 8\), we don’t get back \(9\). We are off by 1. We could also define the remainder as \(r = a - q * b\).
This leads us to a very simple algorithm for computing the remainder. The algorithm given in a function named remainder.
Function remainder(integer a, integer b)
Let q = a / b
Let r = a - q * b
Return r
End Function
We can run this function by hand on paper. When we use a function with specific values, it is referred to as calling the function. What happens when we call the function remainder(9,2). The first command says assign \(q=a/b\). We know that \(a=9\) and \(b=2\) from the function call. The first number is \(9\) and that matches with the first parameter \(a\). This is telling us to compute \(q=9/2=4\).
The second command says assign \(r=a-q * b\). Plugging in the values we get \(r = 9 - 4 * 2 = 1\). The last command says return the value r. What does it mean to return 1? It means we are giving that back as the solution to our computation.
What is the value of remainder(9,2)+4? The value of remainder(9,2) is 1, the return value. We can now do the addition \(1+4=5\) and get our answer.
We might want to compute remainders multiple times in our code. By encapsulating this as a function, we can reuse it as needed. We have an algorithm for how the function works, now we need a program to actually do it.
Once we have a concept of a function, we can create a recursive function. A recursive function is a function that calls itself. This is a second way to create iteration.
Factorial Function¶
One of the classical examples is the factorial function. The fact(n) is the product of all integers from \(1\) to \(n\).
\( \begin{align} \text{fact}(n) = 1*2*3*4*5*6*7*\cdots*n \end{align} \)
We can think of this problem in terms of smaller repeated problems.
For example, I want to solve for fact(5). If I knew the answer to fact(4) then I could multiply that answer by \(5\). The problem fact(4) is strictly less complex then fact(5). Further, to solve fact(4) it would be useful to already know fact(3). We can solve the original problem if we know the solution to a simpler problem.
A recursive case is a way to define a function in terms of smaller versions of itself. Notice that this is a case because it only handles some inputs.
\( \begin{align} \text{fact}(n) =& \text{fact}(n-1) * n & n \ge 0 \end{align} \)
This pattern can’t go on forever. There needs to be a simplest case. Each recursive call makes the problem simpler (like counting down). We can only stop if there is a smallest input. You can count down negative numbers forever. We need a stopping point. This is called the base case. For the factorial function, the smallest input is mathematically defined as fact(0)=1.
\( \begin{align} \text{fact}(1) =& 1 & n=0 \end{align} \)
In general, we may need multiple base cases and recursive cases. For this function, we only need one of each.
Now that we have handled all possible inputs, we can write the recursive definition.
\( \begin{align} \text{fact}(n) =& \begin{cases} \text{fact}(n-1)*n & n > 0 \\ 1 & n=0 \end{cases} \end{align} \)
Next, we can translate this mathematical definition into an algorithm.
Function fact(integer n)
If n == 0 then
Return 1
Else
Return fact(n-1)*n
End If
End Function
How do we use this to compute a value? We can trace the logic of fact(5).
Function Call |
Computation |
Depends on |
Result |
|---|---|---|---|
|
|
|
\(24 * 5 = 120\) |
|
|
|
\(6 * 4 = 24\) |
|
|
|
\(2 * 3 = 6\) |
|
|
|
\(1 * 2=2\) |
|
|
|
\(1 * 1=1\) |
|
|
Nothing |
1 |
The collection of pending function calls is called a call stack. The functions stack up into a pile waiting for answers. The need finish in the opposite order that they were called. The last function call in the recursive call stack will be the first one to complete.
Factorial Runtime Analysis¶
How does our factorial function run? If we give the function an input of \(n\) the best case is \(n=0\). This would only cause the function to execute one time. For larger values, we will need multiple recursive calls. We need to look at how the function input changes.
Pay attention to the value of the input \(n\) in the example from above.
Function Call |
Computation |
Depends on |
Result |
|---|---|---|---|
|
|
|
\(24 * 5 = 120\) |
|
|
|
\(6 * 4 = 24\) |
|
|
|
\(2 * 3 = 6\) |
|
|
|
\(1 * 2=2\) |
|
|
|
\(1 * 1=1\) |
|
|
Nothing |
1 |
Every call decreases the value of \(n\) by 1. It keeps going until n==0 is true. How many times can be subtract 1 from \(n\) before it reaches zero? The answer is \(n\) times! The recursion will execute \(n\) times. This is another linear algorithm. It takes \(O(n)\) time.
Factorial Memory Analysis¶
How much memory is required for our function? Each call just has one integer \(n\) and the return value to keep track of. The problem is that there will be many recursive calls. Every one of them will need to remember the value of \(n\) for its recursive call. Otherwise it will not be able to complete the multiplication. This means the function will not be constant memory usage. At the worst point, it uses \(O(n)\) memory. The memory usage is linear.