Tips to code a Recursion like a Pro
Recursion is a divide-and-conquer approach to solving problems. In Recursion, the problem is divided into Sub-Problems. The sub-problems are easier to solve. Then Solutions to sub-problems are combined to solve the original problem. Here are some awesome tips to code a recursion like a pro.
Tips to Code a Recursion
Make sure the recursion stops
Make sure your condition is approaching towards base case, so if base case is at n==0, make sure every recursive call you make you decrease value of n, so it meet base case eventually.
Use safety counters to prevent infinite recursion
If you’re using recursion in a situation that doesn’t allow a simple test such as the one just described, use a safety counter to prevent infinite recursion. The safety counter has to be a variable that’s not re-created each time you call the routine. Use a class member variable or pass the safety counter as a parameter. Here’s an example:
public int RecursiveFunc(int safetyCounter)
{
if(safetyCounter>SAFETY_LIMIT)
return;
safetyCounter++;
RecursiveFunc(safetyCounter);
}
Limit recursion to one routine
Cyclic recursion (A calls B calls C calls A) is dangerous because it’s hard to detect. Mentally managing recursion that involves many routines is tough. If you have cyclic recursion, you can usually redesign the routines so that the recursion is restricted to a single routine.
Keep an eye on the stack
With recursion, you have no guarantees about how much
stack space your program uses and it’s hard to predict in advance how the program
will behave at run time. You can take a couple of steps to control its run-time behavior,
First, if you use a safety counter, consider how much stack you’re willing to allocate to the recursive routine. Set the safety limit low enough to prevent a stack overflow.
Second, watch for allocation of local variables in recursive functions. Local variables are stored in stack, thereby increasing the size of the stack. As an alternative, use new to create objects on the heap rather than letting the compiler create auto objects on the stack.
Don’t use recursion for Fibonacci numbers
One problem with computer-science textbooks is that they present silly examples of recursion. The typical examples are computing a factorial or computing a Fibonacci sequence. Recursion is a powerful tool, and it’s really dumb to use it in either of those cases.
int Factorial( int number ) {
if ( number == 1 ) {
return 1;
}
else {
return number * Factorial( number - 1 );
}
}
The drawbacks of the above code are,
1)It is Slower than iterative approach
2)Code is hard to understand
3) If recursion is too deep, then there is a danger of running out of space on the stack and ultimately program crashes.
You should always consider iterative approach before using recursion. Sometimes one approach works better; sometimes the other does. Consider both before you choose either one.
These are the points that I have gathered from the Book ‘Code Complete’ written by Steve McConnell. Every Software Engineer Should read this book at least once. It contains lots of guides with real-time usage which can make you a better programmer.
