Recursion is one of the tough programming techniques to master. Many programmers working on both Java and other programming languages like C or C++ struggles to think recursively and figure out the recursive pattern in the problem statement, which makes it is one of the favorite topics of any programming interview. If you are new to Java or just started learning Java programming language and you are looking for some exercise to learn the concept of recursion then this tutorial is for you.
In this programming tutorial, we will see a couple of examples of recursion in Java programs and some programming exercise that will help you to write recursive code in Java-like calculating Factorial, reversing String, and printing Fibonacci series using the recursion technique.
For those who are not familiar with the recursion programming technique here is the short introduction: "Recursion is a programming technique on which a method calls itself to calculate result".
It's not as simple as it looks and mainly depends upon your ability to think recursively. One of the common traits of recursive problems is that they repeat themselves, if you can break a big problem into small junk of repetitive steps then you are on your way to solving it using recursion.
Also, knowledge of essential data structure is also very important and that's why I suggest all Java programmers one of these comprehensive Data structures and Algorithms courses to fill the gaps in your understanding.
For those who are not familiar with the recursion programming technique here is the short introduction: "Recursion is a programming technique on which a method calls itself to calculate result".
It's not as simple as it looks and mainly depends upon your ability to think recursively. One of the common traits of recursive problems is that they repeat themselves, if you can break a big problem into small junk of repetitive steps then you are on your way to solving it using recursion.
Also, knowledge of essential data structure is also very important and that's why I suggest all Java programmers one of these comprehensive Data structures and Algorithms courses to fill the gaps in your understanding.
How to solve a problem using Recursion in Java
In order to solve a problem using recursion in Java or any other programming language e.g. C or C++, You must be able to figure out :
1) The base case, the last point which can be resolve without calling recursive function e.g. in the case of the Fibonacci series it is 1 and 2 where the result will be 1. In the case of a recursive power function, it's zero power which is equal to 1, or in the case of calculating Factorial its factorial of zero which is equal to 1.
2) With every recursive method call, Your problem must reduce and approach the base case. If this is not the case then you won't be able to calculate the result and eventually die with java.lang.StackOverFlowError
1. Recursion Programming Example in Java
In our programming example of recursion in Java, we will calculate the Fibonacci number of giving lengths using recursion. In the case of the Fibonacci number, the current number is the sum of the previous two numbers except for the first and second number which will form the base case for the recursive solution.
public class RecursionTest {
public static void main(String args[]) {
System.out.println("fibonacci series for length 1 is " + fibonacci(6));
}
public static int fibonacci(int number){
if(number < 1){
throw new IllegalArgumentException("Invalid argument for Fibonacci series: "
public static void main(String args[]) {
System.out.println("fibonacci series for length 1 is " + fibonacci(6));
}
public static int fibonacci(int number){
if(number < 1){
throw new IllegalArgumentException("Invalid argument for Fibonacci series: "
+ number);
}
//base case of recursion
if(number == 1 || number == 2){
return 1;
}
//recursive method call in java
return fibonacci(number-2) + fibonacci(number -1);
}
}
}
//base case of recursion
if(number == 1 || number == 2){
return 1;
}
//recursive method call in java
return fibonacci(number-2) + fibonacci(number -1);
}
}
If you look above example of recursion in Java you will find that we have a base case where the program returns a result before calling the recursive function and then with every invocation, the number is decreased by 1. This is very important to reach a solution using the recursive technique.
2. Programming Exercise to solve using Recursion
Anyway, try to solve the following programming exercise by using the Recursion programming technique for better understanding
1. Print Fibonacci series in Java for a given number, see here for a solution
2. Calculate factorial of a given number in Java, sees here for solution of this programming exercise
3. Calculate the power of a given number in java
4. Reverse a String using recursion in Java, see here for a solution
5. Find out if there is a loop in a linked list using recursion
This was a simple introduction of the Recursion programming technique to Java programmers with the most basic examples. There is a lot more to learn on Recursion including different types of recursion e.g. tail recursion, improving the performance of the recursive algorithm using memoization or caching the pre-calculated result, etc.
It is also recommended not to use the recursive method in production code instead write iterative code to avoid any StackOverflow error.
Other programming tutorials from Javarevisited Blog
Hi Javin,
ReplyDeleteI am great fan of your blog.
If I can request you to add a specific topic set then it would be
"Data Structure : Algorithms Interview Questions."
e.g. : Java program on linked list, heap, stacks etc.
@Anonymous, Thanks. I will definitely try to include to Interview questions and Java programs from Data Structure and Algorithms.
ReplyDeleteI like list of programming question on Recursion, that's the best way to learn recursion in Java or any other programming language. Here are few more recursive programming exercise to add into your list :
ReplyDelete1) Write a method to countDown(int number) to print count down using Recursion in Java e.g. countDown(10) will print 10 9 8 7 6 5 4 3 2 1 0
2) Write a method to reverse a Linked List in Java using recursion.
3) Write an method to convert Digits to words in Java using recursion e.g. digitToWord(421) will print four two one in console.
Love to know more about different types of recursion and there benefits e.g. tail recursion, please share.
Unless you memoize the results of your Fibonacci computations, you will be sadly disappointed by the time your application takes. Let's instrument the calls to fibonacci:
ReplyDelete1. Add a timesCalled variable to the class:
private static int timesCalled = 0;
2. Insert an increment at the beginning of the fibonacci method:
timesCalled++;
3. Report it at the end of main:
System.out.println("Fibonacci was called " + timesCalled + " times.");
In fact, if you output the argument at the beginning of each fibonacci call, You will see a tremendous amount of waste. There are two solutions:
1. Store fibonacci(n) in a map as soon as you compute it, and look up fibonacci(n) in the map first. This is called memorization.
2. Use a better algorithm, In this case, a divide-and-conquer algorithm is best.
fibonacci(2*n) == (2 * fibonacci(n-1) + fibonacci(n)) * fibonacci(n).
fibonacci(2*n - 1) = fibonacci(n-1) * fibonacci(n-1) + fibonacci(n) * fibonacci(n).
There are others.
In order to understand Recursion better or use Recursion in your code, you should know how to combine result from individual method calls to generate complete result. E.g. In this recursive Fibonacci method you are adding return value of methods. Some time you may need to multiply it e.g. in case of calculating factorial using recursion, you do n*factorial(n-1)
ReplyDeleteRecursion is not good for production code, it takes more memory and space and be careful of creating arrays in recursive code. The amount of space used can pile up very quickly, as can the amount of time required for memory management.
ReplyDeleteRecursion has its shares of problem e.g. difficult to understand, read and constant worry of stackoverflow error, but it doesn't mean its completely useless. Recursion is very intuitive in many cases e.g. trees, graphs and other recursive data structures, for example path finding algorithms rely on recursion. The problem of stackoverflow error can also be solved by tail call optimization and many JVM language like Scala already does that. By the way, Java is shy way from recursion, even in TreeMap implementation in Java uses non-recursive approach to navigat trees. In short, recursion is bad in many cases but it is also a natural problem solver in other, just like static methods, recursion also has its place in your code base.
ReplyDelete