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.

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.
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.
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.

Java, JavaScript, Open Source enthusiast. Competitive programming, golf, and LoL hobbyist. Carleton College Alumni. www.linkedin.com/in/baedavid

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store