Mastering Recursive Coding

Mastering Recursive Coding

recursion

Recursion is quite a simple topic that all Computer Science students are taught in their first semester at university. Unfortunately, those new to computer science tend to struggle with thinking recursively.

This is mainly because recursive thinking is a completely new way of thinking and most people don’t naturally think recursively. This post explains not only what recursion is and why it is useful but will also give tips on mastering recursive coding.

What does recursion mean exactly

In computer science, a recursive function is one that calls itself. Ideally, with each function call, there is a test on the input causing the function to eventually stop.

A classic example of this recursion is the factorial function given below.

As you can see, the factorial function calls itself repeatedly and each time it tests the input to see if it is equal to 1 and if it is, the recursive function stops.

Infinite recursion on the other hand, is when the recursive function fails to stop recursing. Unless the design specification for the function says it should abuse resources and crash things, infinite recursion indicates there’s a bug in the software.

How is recursion useful in programming

The main reason to use recursion is that it presents shorter and neater code which is easier to understand and debug. An algorithm that can naturally be expressed recursively may not be as easy to understand if expressed iteratively.

For example, the recursive function below,

is the same as this non-recursive function,

See how much shorter the recursive function is? In fact, chances are you already know what a factorial function is supposed to do so you found both versions of the code easy to understand. But if I had named them something ambiguous like ‘functionA’, would you have been able to understand what each function is doing? You would probably struggle to describe what the non-recursive function does.

When to use recursion

Every iterative function can be written with a recursive function and because recursion is neater, many people want to use it in place of iteration all the time.

However, recursive functions can very easily become inefficient. Therefore, it is advised to only use recursion when you know the number of recursive calls isn’t excessive. Let me explain why.

You see, imperative languages such as C, C++, Basic, Python, Ruby, Java, and C# will always allocate a single chunk of memory for their stack at the start of each function call. This takes time and resources.

If your recursive function is called 1 million times, it means a single chunk of memory must be allocated at least 1 million times. If you have a stack limit that does not accommodate this, you will end up with a Stack Overflow error.

Therefore, recursion only works if the number of recursive calls is in line with your memory limits. If you are unsure of how your recursive function will perform, check out this post on how to calculate this using the Big O Analysis.

How to code recursively

There are 5 steps to practice when trying to master recursive coding.

1. Determine if problem can be solved recursively

There’s nothing worse than spending hours trying to write a recursive function only to discover that it cannot be done for the problem you want to solve. So first and foremost you want to check that the problem is indeed solvable by recursion.

You know a problem can be solved recursively if the same algorithm occurs more than once. For instance, adding the first 5 numbers is 1 + 2 + 3 + 4 + 5. Addition is happening more than once so this problem can be solved recursively.

2. Pick a base case

A base case is the smallest possible input on top of which the recursion is built. It is basically a test that guarantees that the recursion will eventually end.

For example, if we are trying to add the first N numbers, some possible base cases are N=0, N=1, N=2. If we choose N=2, we are doing 1 + 2 but this is not the smallest possible base case. N=1 is a smaller base case which returns 1 but N=0 is even smaller and returns 0. N=-1 is invalid because we cannot find the first -1 numbers. So, N=0 would be the smallest possible base case.

3. Decide how you want your original input to reach the base case

The next step is figuring out how exactly your first input gets to the base case. Is it divided by 2 at each call? Or multiplied by itself? How exactly do you guarantee that the base case is reached? Write a function that will execute this function call.

In the example of adding the first 5 integers, if the base case is 0 and the initial input is 5, we get to 0 by subtracting 1 each time we recur through the program. So with each recursive call, N-1 should be called

4. Do some work before or after the recursive call

It is important not to forget to actually do some work on the input at each call. Otherwise you are just recurring for the sake of recurring which is quite a waste of memory.

In our example, we want to make sure that the input is added at each recursive call.

5. Put them together

Lastly, you must paste the base case and the recursive call together. Following the same example of adding the first N integers, that means the following:

Examples

EXAMPLE 1
Write a recursive method that takes as parameters a String s and an integer i and returns a String that has s repeated i times. For example, if the given string is “ZedCoder ” and the integer is 3 then the return value would be “ZedCoder ZedCoder ZedCoder “.

Step 1: Determine if problem can be solved recursively
The print function is happening more than once so this problem can be solved recursively.

Step 2: Pick a base case
The smallest possible integer is 0. So (int n=0) is the base case.

Step 3: Decide how you want your original input to reach the base case
Integer N reaches 0 by subtracting 1 at each call. function(n-1)

Step 4: Do some work before or after the recursive call
Before each call, the String should be printed. So we return String + something.

Step 5: Put them together

EXAMPLE 2
Write a function that, given two words, returns true if all the letters of the first word are contained in the second.

Step 1: Determine if problem can be solved recursively
For each character of the second word, we check if any character of the first word is equal to it. This check function is happening more than once so this problem can be solved recursively.

Step 2: Pick a base case
The smallest possible input for the first String i is the empty string, ” “, and the smallest possible input for the second String s is the empty string, ” “. String s has to reach the base case ” ” in order to prove that each character has been checked. However, String i only reaches the base case if all its characters appear in String s.

If a character in String i appears in String s, we will remove that character from String i. Therefore, at the end of the entire function, the only characters remaining in String i are those which do not appear in String s.

The following image describes exactly what is happening in this example

example2

Therefore, there are two tests to run. One will check if (String s=”” AND String i=””) while the next will test if (String s=”” AND String i != “”)

Step 3: Decide how you want your original input to reach the base case
String s reaches “” by calling s.substring at each recursive call. String i reaches “” by replacing its characters with an empty char ‘ ‘.

Step 4: Do some work before or after the recursive call
Before each call, we must check if the character at position 0 for String s is equal to any of the characters of String i. We do this with a for loop.

Step 5: Put them together

Practice questions

Here are some questions you can do to practice recursion on your own.

1. Write a recursive method that takes as parameters an initial investment amount, an annual interest rate, and a number of years. The method should return the value of the investment after the given number of years, assuming that the interest is compounded annually. (For example, if the initial investment is 1000 and the interest rate is 10 percent, then after one year the investment will be worth 1100, after two years 1210, after three years 1331, etc.)

2. Write a recursive method that takes as parameters an initial loan amount, an annual interest rate, a monthly payment, and a number of months. The method should return the amount that is still owed after the given number of months, assuming that the interest is compounded monthly. (That is, each month 1/12 of the annual interest rate is charged and the monthly payment is subtracted from the loan amount.)

3. Write a recursive method that takes as parameters a String s and an integer i and returns a String that has s repeated 2^i times. For example, if the given string is “Go bears! ” and the integer is 3 then the return value would be “Go bears! Go bears! Go bears! Go bears! Go bears! Go bears! Go bears! Go bears!”. Do not use multiplication or exponentiation in your algorithm. Just double the length of the string i times.

4. Given a string, compute recursively (no loops) a new string where all the lowercase ‘x’ chars have been changed to ‘y’ chars.

5. We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.


What did you think of this post? Leave your comments below…

Seda
Seda Kunda is a web designer and developer with a degree in Computer Science and a great passion for code. Besides code, she enjoys pepperoni pizza, watching the bachelor and sleeping in on Saturdays.
Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn