One of the hardest concepts for a beginner programmer to grasp is recursion, especially if you are a self-taught developer and never formally studied computer science in school/college. Despite the steep learning curve with this concept, mastering recursion is vital in your programming journey to become a "good programmer".
However, it can quite tricky to wrap one's head around initially and many find it very hard to solve a problem recursively.
So, in this article we will learn what is recursion, why is it required and how we can solve recursive problems with ease.
What is recursion?
In simpler terms, recursion is the process of solving a problem in terms of a smaller version of the same problem. It involves making a function call to itself until it encounters a condition provided by the programmer (base case) and terminates the function call.
Example: Program to add all of the numbers up to 10 using recursion.
public class Main {
public static void main(String[] args) {
int result = sum(10);
System.out.println(result);
}
public static int sum(int k) {
if (k > 0) //base case
return k + sum(k - 1);
} else {
return 0;
}
}
}
Why base condition is so important in recursion?
The condition where our recursive function will stop making new function calls to itself is called the base condition. If there is no base condition in a recursive problem then, there will be an infinite recursive call from which a function cannot return. This will cause the stack memory to be filled again and again and a time will come when it exceeds the computer memory giving us a stack overflow error.
Why Recursion?
Recursion is made for solving problems that can be broken down into smaller, repetitive problems. It is especially suitable for working on things that have many possible branches (eg- Fibonacci sequence) and are too complex for an iterative approach.
How to understand and approach a recursive problem?
Identify the problem and how can it be broken down into the smaller problem
Write the recurrence relation of the problem, and if needed draw the recursive tree
Track the flow of functions in pen and paper (v imp)
Furthermore, also use the debugger to track the flow of the program
By tracking the flow of the program, analyze the recursive function and identify what value is currently being used in the function call
See how the value is returned to each step.
Ask three questions before solving the recursive problem
While solving a recursive problem be mindful of three questions.
What is the base case for this problem?
Answer: The base case for a problem is often the one provided by the question itself.
Is each function call making the problem smaller?
Answer: Yes, each recursive call is making the original problem decrementing leading to the base case.
Does the algorithm of the smaller case work correctly for the general case?
Answer: Yes, the recursive call gives the correct value, and the return statement computes it in the base case.
Conclusion
In conclusion, recursion is a vital aspect of the programming journey that requires patience and practice to master. Although it may be difficult to grasp at first, breaking down complex problems into smaller self-similar problems and tracking the program flow through pen and paper or a debugger can help.
As you become more experienced, you will eventually be able to perform these steps in your mind without the need for explicit documentation.
To truly understand recursion, it is important to persistently practice and become familiar with its underlying principles. So, just stick with it, practice, and practice a lot; that's the only way you can truly get the hang of it.