Thursday, December 27, 2012

Recursion in Java with example – Programming Techniques Tutorial

Recursion is one of the tough programming technique to master. Many programmers working on both Java and other programming language like C or C++ struggles to think recursively and figure out recursive pattern in problem statement, which makes it is one of the favorite topic of any programming interview. If you are new in Java or just started learning Java programming language and you are looking for some exercise to learn concept of recursion than this tutorial is for you. In this programming tutorial we will see couple of example of recursion in Java programs and some programming exercise which will help you to write recursive code in Java e.g. calculating Factorial, reversing String and printing Fibonacci series using recursion technique. For those who are not familiar with recursion programming technique here is the short introduction: "Recursion is a programming technique on which a method call itself to calculate result". Its not as simple as it look and mainly depends upon your ability to think recursively. One of the common trait of recursive problem is that they repeat itself, if you can break a big problem into small junk of repetitive steps then you are on your way to solve it using recursion.


How to solve problem using Recursion in Java

Recursion in Java programming with Example technique
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) Base case, last point which can be resolve without calling recursive function e.g. in case of Fibonacci series its
1 and 2 where result will be 1. In case of recursive power function its zero power which is equal to 1 or in 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 to base case. If this is not the case than you won't be able to calculate result and eventually die with java.lang.StackOverFlowError

Recursion Programming Example in Java
In our programming example of recursion in Java we will calculate Fibonacci number of give length using recursion. In case of Fibonacci number current number is sum of previous two number except first and second number which will form base
case for 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: "
                                                + number);
        }
        //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 program returns result before calling recursive function and than with every invocation number is decreased by 1. This is very important to reach solution using recursive technique.

Programming Exercise to solve using Recursion
Here are few more programming exercise to learn Recursion programming technique in Java programming language. This exercise are solely for practicing. In order to understand Recursion properly you must try to think recursive e.g. look tree as collection of small tree, look string as collecting of small String, look staircases as collection of small staircase etc. Any way try to solve following programming exercise by using Recursion programming technique for better understanding

1. Print Fibonacci series in Java for a given number,  see here for solution
2. Calculate factorial of a give number in Java,  see here for solution of this programming exercise
3. Calculate power of a give number in java
4. Reverse a String using recursion in Java, see here for solution
5. Find out if there is a loop in linked list using recursion

This was simple introduction of Recursion programming technique to Java programmer with most basic examples. There are lot more to learn on Recursion including different types of recursion e.g. tail recursion, improving performance of recursive algorithm using memoization or caching pre calculated result etc. Its also recommended not to use recursive method in production code instead write iterative code to avoid any stackoverflow error.


Other programming tutorials from Javarevisited Blog

6 comments :

Anonymous said...

Hi Javin,

I 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.

Javin @ CyclicBarrier Example Java said...

@Anonymous, Thanks. I will definitely try to include to Interview questions and Java programs from Data Structure and Algorithms.

sachin said...

I 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 :

1) 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.

Eric Jablow said...

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:

1. 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.

Rajni said...

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)

Anonymous said...

Recursion 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.

Post a Comment