JonMifsud
Web Developer & Consultant

Recursion: an Introduction to Recursive Methods

31 December 2012

Recursion put simply is another way to work instead of using loops. A suitable replacement for while-do loops, recursion can also be a much simpler and neater solution.

What are the basics of Recursion

Recursion is based on the Divide and conquer methodology, similar to organisational chains when using divide and conquer you always try to give the work to someone else and you just take care of the aggregation. The only time when you cannot really be lazy and re-assign the work is when you are at the bottom of the food chain. A simple example would be if you had to calculate the number of employees who are under a particular division you could do two things. One in an old fashioned way calculate by starting from the managers and checking employees directly reporting to them until you get to the bottom of the chain, or otherwise issue a directive to the manager to calculate this, should the manager do the same with all his directly reporting employees the recursive process looks much simpler.

What do you need to use Recursion

The basics for recursion are very simple, you need to define what is called a base-case. That is if you are at the bottom of the food-chain what will you do, and if you are not what exactly will you ask for. In the above use-case the employee who manages no other employee will say I manage no employees sorry. The second bit is what to do with the results obtained from the recursion, so if the manager asked his employees how many employees they manage, he has to then return the number each of his employees manage + one (the employee who is asked) and return it to his manager.

Can Recursion be used in non Object Oriented Approaches

Yes sure, its done in the same way. The previous recursive example we used people and uses an object oriented approach. However the most simple example ever used is the factorial example which is a normal function. A factorial function is a function which is supposed to multiply the number given with all the smaller integers down to the value of 1. So a factorial of 5 would be equal to 54321 (some leave out the final x1 as it doesn't alter the number but for completness sake we include it). The easiest way to build this function is indeed using recursion, the function is defined to have a single parameter (the number you want the factorial of), you have a base-case that when the number is equal to 1 you return itself, if its not 1, all you have to do is multiply it by the result of the factorial of the number minus 1.

A basic recursive example in Pseudo Code

              function factorial(number){
    if (number == 1)
        //this is the base case if the number is one we just return the number
        return number; //same as return 1
    else //the recursive case
        //if number is not 1 we multiply the number by the result of the factorial calculation of the number - 1.
        return factorial(number - 1) * number;
}

            

How would it look like if I did not use recursion?

              function factorial(number){
    variable total = 1;
    //initialize the total value and start a loop to loop over all the numbers
    for-each (integer count = 1; count <= number; count++){
        //multiply current number to the total
        total = total * count;
    }
    return total;
}

            

The above is a simple case - both methods work however the recursive example is neater and easier to understand; does not require the complexity of loops and is thus easier to understand. Recursion is known to be the factor that distinguishes good and excellent developers from average ones. This article was supposed to provide the basics to help you understand the difference of recursion to standard loops, full advantages of recursion are not given but if well understood and well used recursion can give a lot of advantages. From leaner and simpler code, to more efficient evaluations; Recursion, and divide and conquer methodologies are indeed used in various efficient sorting and searching algorithms among other things. If you really want to stand out from the crowd I suggest you Introduce yourself to recursion and take it for a good ride, then come back and chip in with your questions and feedback.

For those asking which languages support recursion - Recursion can be used in any programming languages where you have objects or functions that take parameters, C, C++, Java, Javascript, PHP, XSLT and all other programming and reasoning languages you can think of support recursion. So whatever language you practice recursive functions are guaranteed to be a good methodology to master.

Written by Jonathan Mifsud

Jonathan Mifsud is a web developer by day and an SEO enthusiast by night. He provides freelance web development and consultancy services and is available for hire. You can get in touch with him on twitter and Google+

Comments

Leave a Comment

There are no comments made so far.

Post a new Comment

Please write your name.
Please enter your comment
Please enter your email address.