Taking the First Recursive Leap of Faith

// 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]);
1. Go through the array one element at a time.
2. Print out each element
3. If we have printed our last element, stop.
1. Print out the first element of the subarray.
2. Continue to the next subarray.
3. Exit when the subarray is empty.
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. }
  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.
Given the sequence: 1 1 2 3 5 8 13
find the nth number in the sequence
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)
  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)
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. }
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.
  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
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. }

--

--

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
David Bae

David Bae

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