Learning recursion with simple example
Introduction
As you’re aware that recursion forms building block for most of the popular algorithms like Binary search tree traversals, N-Queen problem, subset of a given sum, 0–1 knapsack etc. to name a few. In this post I would like solve String reversal problem using recursion with explanation.
Basics
In simple terms, recursion refers to calling a function by itself. Let’s say we have an entry point function main() and main() calls function A(). Based upon task we want to achieve function A() calls itself until our task is completed. In recursion, we break our task into smaller different tasks and continue working on them. For recursion to work, we should have a base case (or a terminating case), which terminates the recursion. And we should have an induction case (breaking our task into smaller tasks to solve it).
Recursion helps to break complex problem into smaller chunks and makes code concise.
Each function call is called as an “Activation Record” (AR), which is placed on call stack.
Program to explain recursion
Let’s study below simple String reversal program in Java to learn basics of recursion.
In this program we want to reverse a String “ABC” to “CBA”. For simplicity and to explain the topic, I have used built-in method length(), substring(), charAt() from String class.
public class Test {
static String reverseString (String s) {
if (s.length() == 0) {
return s;
}
return reverseString (s.substring(1)) + s.charAt(0);
} public static void main(String[] args) {
String reverse = reverseString ("ABC");
System.out.println("reverseString = "+reverse);
}
}
The code starts from main calling reverseString (“ABC”).
The reverseString() returns a String
The reverseString() has
1) Base case: if (s.length() == 0) which ends the recursion. End of recursion is marked by statement return s.
2) Induction case: reverseString (s.substring(1)) which continues the recursion
So let’s see below Activation Record diagram to follow step by step when reverseString call happens from main().
“Solve” task breaks s into smaller units & creates a new Activation Record on call stack.
“Return” returns the result of current execution to previous caller.
The return result of current execution is shown by below in the diagram
Please follow this symbol in above Activation Record diagram.
When CALLER, the main() makes a call reverseString (“ABC”) the call execution proceeds as below:
In each call to reverseString (s), we check if s.length() == 0, this is our recursion termination condition. If s.length() == 0 condition evaluates to be false, then reverseString() calls itself by taking s.substring(1) of current s as an argument. This is called as induction case of recursion. So in each respective recursive call to reverseString, we break our input String into smaller chunk i.e. reducing current string by 1 (by doing substring) until s becomes empty. This is also called as Top-down approach to a problem.
How the subsequent recursive calls return to the CALLER
The return values from previous reverseString recursive calls are highlighted in yellow color for clarity.
This is how call hierarchy comes to an end by assigning String reverse = “CBA”.
The next line prints string reverse to the console.
Conclusion
A recursive function must have a base case to terminate it. Otherwise, you will get stack overflow error, as call never returns to caller.
Recursion makes use of stack for its execution
Recursion helps to write concise code to solve complex problems
I hope this article will be helpful for beginners who want to learn recursion and apply it to complex problems.
Thank you!
