Taking the First Recursive Leap of Faith

Recursion is a concept that is unnecessarily feared by new programmers. Much like the movie Jaws and the fear of sharks, recursion is scary because of 2nd year CS students complaining to 1st years about how difficult it is.

What they fail to mention is how prevalent it is in the world. The mathematical constant, the Golden Ratio, is recursive. The famous Sieve Triangle, a triangle made up of 3 sub triangles which are all made up from sub triangles, is recursive. Strings, arrays, lists, trees, graphs are all recursive.

From the first day that we are introduced to programming we are taught to think iteratively. Take the humble for loop for example:

// We are given an array and want to print out every element in it
// [1,2,3,4,5]
// We can accomplish this by creating a for loop to iterate through // each element
for(int i = 0; i < A.length; i++)
    print(A[i]);

If we were to put the above code into plain english it would read something like this:

1. Go through the array one element at a time.
2. Print out each element
3. If we have printed our last element, stop.

But is this really the only way to this? What if we tell it to print out the first element of each subarray?

1. Print out the first element of the subarray.
2. Continue to the next subarray.
3. Exit when the subarray is empty.

The above example is an incredibly simplified example of recursion. If we were to translate it into code it would look like this:

1. void printArray(int[] array, int first) {
2.     if(first == array.length)
3.         return;
4.     print(array[first]);
5.     printArray(subArray(array(1)), first);
6. }

So what exactly is recursion? Recursion in computer science is simply a function that makes calls itself in its declaration. In line 5 of the above example, we call printArray before we even finish defining it.

So how does this work? Recursion takes in initial parameters and then manipulates them into smaller, more workable problems.

Taking Eric Roberts’s work Thinking Recursively in Java and Manuel Rubio-Sánchez’s work Introduction to Recursive Programming, we can simplify recursion to 6 simple steps.

1. Determine the size of the problem
   Recursion, like any other function, works off the parameters we give it. By finding the size of the problem we need to work with, we are able to come up with smaller and more solvable recursive cases.
2. Find the base cases
   When we manipulate the size of the problem we want to solve, we must define the base case(s). The base case is the mathematical equivalent to the given. Because the size of the problem is so trivial, we can easily solve it without any computations. Using these base answers, we can begin building up to our recursive solution.
3. Create smaller instances of the problem
   Any problem that is recursive in nature will have smaller instances of the problem. Smaller instances are similar to the main larger problem, just easier to solve and manipulate.
4. Find the recursive case
   Just because we know we need to create smaller problems does not mean that we can just mindlessly create smaller problems. We must create smaller recursive problems, that we can then use to find a solution.
   For those who are more math savvy this would be the equivalent to a recurrence relation.
5. Assemble the code
   Now that we have assembled all the tools we need, we can begin combining them to create our recursive program.
6. Prove it works
   Now that we have typed up a recursive program, we must now prove that it works. This can be done in a variety of ways from running basic tests to proving the math via induction.

Now that we have established how to write a recursive program, let’s go ahead and try a few problems out. The problems are ordered in ascending levels of difficulty.

Given the sequence: 1 1 2 3 5 8 13
find the nth number in the sequence

If the above sequence looks familiar thats because it’s the Fibonacci Sequence! The Fibonacci Sequence is a sequence of numbers where any number in the sequence is equal to the sum of the last two numbers in the sequence. We can say that:

The nth number is equal to n - 1 + n - 2 OR 
when n = 0, f(0) = 0 AND n = 1, f(1) = 1
ELSE when n > 1, f(n) = f(n - 1) + f(n - 2)

Let’s begin breaking down this sequence via the 5 steps that Rubio and Roberts proposed.

1. Determine the size of the problem
   Thankfully, the problem gives us the size. The nth number is the size of our problem. We can now begin to theorize smaller subproblems we can solve.
2. Find the base cases
   There are two potential sets of base cases. The first more naive set is n = 1 return 1 and n = 2 return 1 . We found this just by observing the first two numbers of the sequence. However, what would happen if a user passed a 0 into this function? The program would be quite unhappy as we haven’t defined what to do when it is passed a 0.
   
   We want to create programs that are generalized in nature so that there are less bugs and less code overall. Instead of setting our base cases to
   [1, 1], we can set them to n = 0 return 0 and n = 1 return 1to create a buffer for user error.
3. Creating smaller instances of the problem
   We know that smaller instances of the Fibonacci sequence are simply f(n) — x ≥ 0where x is a random natural number.
4. Finding the recursive case
   We defined the recursive case earlier and we didn’t even know! We said that the nth number in the Fibonacci sequence is equal to
   f(n — 1) + f(n — 2). This expression is our recursive case that we can call to find any number in the sequence.
5. Assemble the code
   Let’s begin assembling the code. If we pretend that the code box below is a table and we laid out all the parts we need for this program it will look like this:

Size of the problem: nth number of the sequence
 Base Case: f(0) = 0 AND f(1) = 1
 Recursive Case: for any n > 1, f(n) = f(n - 1) + f(n - 2)

Let’s combine the pieces now. We begin with declaring our function and setting our base cases. We then add our recursive case for when the parameter we pass does not fulfill the base case conditions.

1. int fibonacciSequence(int n) {
2.     // Our base cases
3.     if(n == 0)
4.         return 0;
5.     if(n == 1)
6.         return 1;
7.     // Our recursive case
8.     else
9.       return fibonacciSequence(n - 1) + fibonacciSequence(n - 2);
10. }

Congratulations! We have written our first recursive program to find the nth number in the Fibonacci Sequence. Before we continue some readers may have noticed that we return the recursive call in line 9, but we did not return the recursive call for our program that prints out an array. This is because of how recursion works in the memory stack.

Whenever we make a recursive call, that call gets added to the memory stack. We continue to push recursive calls onto the stack with changing parameters until we reach our base case.

When we reach our base case, we return that value into the initial recursive call that called it. We’ll denote that recursive call with R. We must then return the value from call R into the recursive call that called it. We will denote that call with R`. R` must now return its value into the recursive call that called it. Let’s denote that call as R``. This recursive chaining of returns continues until we reach the very first recursive call where we return our answer. If we do not return any of our recursive calls, our recursive program will not have access to the previously computed variables leading to a blank output.

Having this extra bit of knowledge let’s go to the next problem.

We are given an array of coins called coins. We are also given an integer c, where we must return the minimum number of coins to make exact change for c using the array coins.

Let’s start solving this problem by using the 5 steps earlier:

1. Determine the size of the problem
   The size of the problem is a little bit more ambiguous here. We are given two parameters where we must use both of them to find the minimum number of coins to make change for c. Inspecting the problem closely, we see that the size of the problem is c because we are making change for it.
2. Find the base cases
   Our base case here is simple if we ask ourselves this question:
   What is the number of coins we must return when asked to make change for 0?
   The obvious answer here is 0. When attempting to make change for 0, the best we can do is 0 coins.
3. Creating smaller instances of the problem
   Let’s assume in the problem we are given 6 as the target to make change for. Before even thinking about the array of coins, we can assume that
   6 — n, where 0 < n < 6, is a smaller instance of the problem. If we were to subtract 2 from 6, we would have 4 left over, leading to the exact same problem, just with a different target.
4. Finding the recursive case
   We sort of defined the recursive case in step 3. Let’s be more explicit this time.
   Our recursive case is whenever our target c is not 0. Any time we are given a c that is greater than or equal to 0, c — n is also a recursive case. To put it into more plain english, using the example from above, when we subtract 2 from 6 and are left with 4, we must make the same computations for 4 to find the number of coins for 6. This continues until we reach c = 0.
5. Assemble the code
   Let’s begin begin assembling the code again. Below us we have the pieces we need to create our recursive solution.

Size: c where c is the target we must make change for
 Base Case: When c = 0 return 0
 Recursive Case: When c >= 0

Looking at our “tool box” we see that there aren’t actually too many things to work with here. This is because we have yet to mention the array coins. By subtracting each coin from c, we are able to create our recursive cases.

1. int makingChange(int[] coins, int c) {
2.    // Declare our base case
3.    if(c == 0)
4.        return 0;
5.    // Placeholder for our minimum number of coins
6.    int minCoins = Infinity;
7.    // Loop through our coins array subtracting each coin from c
8.    for(int i = 0; i < coins.length; i++) {
9.    // If the subtracted coin is larger than 0 recursively call it
10.          if(c - coins[i] >= 0) {    
11.           int currentMinCoins = makingChange(c - coins[i]);
12.           if(currentMinCoins < minCoins)
13.               minCoins = currentMinCoins
14.       }
15.   return minCoins + 1;
16. }

In lines 3–4, we declare our base case to exit our future recursive calls.

In line 8, we begin looping through our array of coins. Each loop we subtract the value coins[i] from c. If the remainder is greater than or equal to 0, we recursively find the minimum coins for the remainder.

If that recursive call’s minimum coins is less than the current minimum coin, we set the new minimum coin to what we found.

In line 16, we return our minimum coin + 1, because every recursive call that returns the minimum coins is for c - coins[i]. So to find the minimum coins for c we must add 1 to it every time we terminate out of a recursive call.

Recursion ultimately is a simple concept with difficult execution. However its ability to condense code and produce more readable code makes it a skill that should not be neglected.

Much of computer science and development utilizes recursion, from algorithm design concepts(dynamic programming, greedy algorithms) to data traversal (min-spanning tree, DFS, BFS). As daunting and difficult it may seem, it just takes a recursive leap of faith to begin the journey of recursive programming.