Thought process for writing recursive methods

I was interviewing one candidate the other day and found that he is facing difficulties in writing a recursive method. This is not the first time I am seeing people facing problems with recursion. In this post, I will try to explain the thought process to write recursive methods.

This post is intended for beginners who don’t have any idea about recursion. If you are an intermediate or above level, you don’t find this as useful.

Linear recursion – The popular factorial problem

Factorial problem is very common and I believe every programmer should be able to write one(recursive or non-recursive version) within the time limit of an interview.

Here is what wikipedia says about factorial,

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

5 factorial (5!)

5 factorial (5!)

and

6 factorial(6!)

6 factorial(6!)

The first step for writing a recursive function is to identify the exit condition. Exit condition is needed to stop the recursion and come out from the method.

In factorial, 0! is defined as 1 and this can be used as our exit condition. Once the exit condition is ready, we can write the initial version of the factorial method.

int factorial(int num)
{
    if (num == 0)
        return 1;
}

Above code calculates 0!. To calculate 5!, think it in this way.

If number is not 0, then calculate factorial(4) and multiply with 5.
If number is not 0, then calculate factorial(3) and multiply with 4.
If number is not 0, then calculate factorial(2) and multiply with 3.
If number is not 0, then calculate factorial(1) and multiply with 2.
If number is not 0, then calculate factorial(0) and multiply with 1.

Now you know that factorial(n) is factorial(n-1) * n. With this, we can write the final version of our code.

int factorial(int num)
{
    if (num == 0)
        return 1;
    else
        return num * factorial(num - 1);
}

This is the most simplest form of recursion and often called as Linear recursion. Let us consider another bit complex example of Linear recursion, Reversing an array.

As we discussed above, first step is to identify the exit condition. In this case, it is endIndex < 0. To reverse an array which has 3 elements, you need to iterate the array and swap the values.


A[0] = A[3]
A[1] = A[2]
A[2] = A[1]
A[3] = A[0]

To generalize this, one can say


A[index] = A[lastElementIndex]
A[index + 1] = A[lastElementIndex - 1]
....

With this information, we can write a recursive array reverse method like,

void Reverse(string[] array, int beginIndex, int endIndex)
{
if (endIndex < 0) return; else { Swap(array, beginIndex, endIndex); Reverse(array, beginIndex + 1, endIndex - 1); } } void Swap(string[] array, int beginIndex, int endIndex) { string temp = array[beginIndex]; array[beginIndex] = array[endIndex]; array[endIndex] = temp; } [/sourcecode] This code uses another concept known as Tail Recursion. Data Structures and Algorithms in JAVA defines tail recursion as


An algorithm uses tail recursion if it uses linear recursion and the algorithm makes a recursive call as its very last operation. It is not enough that the last statement in the method definition include a recursive call, however. In order for a method to use tail recursion, the recursive call must be absolutely the last thing the method does

Look at our previous factorial example. It does a recursive call at the last line (return num * factorial(num - 1)). Is that using tail recursion? NO. In this case, recursive call is not the last thing this method does. It is doing the calculation as last thing and can’t be classified as tail recursion.

Experts says that, algorithms that uses tail recursion can easily be converted into a non-recursive one. Converting our array reverse problem to a non-recursive version is left to the reader as an exercise .

Binary recursion – Calculating Fibonacci number

Binary recursion is a more complex form of recursion. When your method does two recursive calls, it can be classified as binary recursion. Consider finding a Fibonacci number.

As a first step, we need to define the exit condition. By definition, Fibonacci(0) is 0 and Fibonacci(1) is 1. This can be used an exit condition. With this, here is the first version of our code.

int fibonocci(int num)
{
if (num <= 1) return num; } [/sourcecode] Next step is to make the formula for calculating Fibonacci(n). To find Fibonacci(3), one may write,


Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
Fibonacci(2) = Fibonacci(1) + Fibonacci(0)
Fibonacci(1) = 1
Fibonacci(0) = 0

In general,


Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)

This formula can be converted into code and we have final version like,

int fibonocci(int num)
{
if (num <= 1) return num; else return fibonocci(num - 1) + fibonocci(num - 2); } [/sourcecode] Let us see a bit complex binary recursion example, calculating the excel column name from it's column number. In excel, columns are numbered like A,B,C,D,….,Z,AA,AB…..AZ,BA etc. Our function should return A for column number 1, B for column number 2 and so on. The first step is to break this into small problem and calculating the exit condition.

We can only calculate a column name if the column number is less than or equal to 26. So that should be our exit condition. If column number supplied is less than or equal to 26, calculate the column name from the number and return. Once the exit condition is ready, we are good to write the initial version of code which can calculate column name up to number 26.

string GetColumnName(int columnIndex)
{
if (columnIndex <= 26) return char.ConvertFromUtf32(columnIndex + 64); } [/sourcecode] Its time to think about the calculations when number is greater than 26. Write down the input and expected output like,


GetColumnName(27) = AA
GetColumnName(28) = AB
GetColumnName(29) = AC
...

You should be able to see the pattern here. The pattern is,


GetColumnName(27) = GetColumnName(27 / 26) + GetColumnName(27 mod 26)
GetColumnName(28) = GetColumnName(28 / 26) + GetColumnName(28 mod 26)
GetColumnName(29) = GetColumnName(29 / 26) + GetColumnName(29 mod 26)
GetColumnName(n) = GetColumnName(n / 26) + GetColumnName(n mod 26)

Now let us write the final version of code,

string GetColumnName(int columnIndex)
{
if (columnIndex <= 26) return char.ConvertFromUtf32(columnIndex + 64); else { int mod = columnIndex % 26; int div = columnIndex / 26; return GetColumnName(div) + GetColumnName(mod == 0 ? 1 : mod); } } [/sourcecode] I hope this post helped you to understand recursion. Any feedbacks are most welcome. Happy programming!

Advertisements

8 thoughts on “Thought process for writing recursive methods

  1. Pingback: How small code optimizations can improve the performance and storage requirements « {love to code?}

  2. Could you please explain more complex algorithms and thought process behind them ? These are very general algorithms you explained but very helpful. Thanks

  3. The article is very helping. Thanks a lot sir.
    Sir, can you please help us identify the “appropriate exit condition” for any given problem. It’s difficult to arrive at the correct “exit condition”.. so.. can you please try explaining the logic behind selection of “exit conditions”?? please…

    Thanks in Advance,
    Roopa

  4. This was really helpful. I was taking too much to work with….Simply thinking of the exit scenario first works wonders. Thank you!!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s