This is a one off post that will educate you on a fairly complex topic in programming. I’d like to preface this by saying that the need to use Java recursion programming does not come up often. I think in my entire professional career I’ve used one recursive algorithm, though your mileage may vary of course.

So what is Java recursion? In computer programming its the process of having a method continually call itself until a defined point of termination.

Lets consider the following recursive code:

public int myRecursiveMethod () { int aVariable = myRecursiveMethod(); }

**Warning**: Don’t actually try to execute this code, as it will never stop.

What sort of conclusions could you draw from this code snippet?

Well the first thing you should take note of is the name of the method: `myRecursiveMethod`

. This is just a random name that I chose to use for this method…nothing special going on there… But, take a look at what we’re doing inside the method: we’re calling a method named `myRecursiveMethod`

. Notice anything special there? **Yes**, that’s the same method name!

So what happens?

Recursion!

The method will call itself, and it will execute the code inside, which is to call itself, so it will execute the code inside of that method, which is to call itself, so it will execute that code, which is to call itself… You see what I’m getting at here?

This code is missing a terminating condition, this is why it will run forever. So how about we include a terminating condition?

public int myRecursiveMethod (int aVariable) { System.out.println(aVariable); aVariable--; if (aVariable == 0) return 0; return myRecursiveMethod(aVariable); }

Now with this method, we’ve introduced a terminating condition. Can you spot it?

When our `int`

variable holds the value `0`

, then this method will not call itself and instead it will simply exit out of the flow. This can be seen from the `return 0`

statement.

So now we’re in a position where this method will continually call itself with a decrementing value of `aVariable`

. So once `aVariable`

hits zero, our recursive method is done!

Can you guess what the output would be if we called this method like so:

`myRecursiveMethod (10)`

Think about it, try and follow through the code line by line and see what conclusions you can come to… once you’ve made a guess, go ahead and create a Class file with a `main`

method and throw `myRecursiveMethod`

in the mix and call it (you’ll need to make the method `static`

).

Once you’ve run the program, if you have NO clue what’s going on behind the scenes, then I’d suggest debugging by throwing a breakpoint in where the method begins. Step through the code line by line and see what happens (it will clear things up).

## So why use Java Recursion?

There are certain problems that just make sense to solve via Java recursion. This is the case because sometimes, when solving problems recursively, you can really cut down on code with your solutions. For example lets take a look at something called the Fibonacci sequence. Here are the first few numbers of this sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21…

If you’ve never seen the Fibonacci sequence before, then can you figure out what’s going on here?

Well, I’m about to explain it, so if you want to try and figure it out on your own, then stop reading.

Here’s how it works:

The 3rd number is the sum of numbers 1 and 2 (0+1=1).

The 4th number is the sum of numbers 2 and 3 (1+1=2).

The 5th number is the sum of numbers 3 and 4 (1+2=3).

The 6th number is the sum of numbers 4 and 5 (2+3=5).

etc.

What’s neat about this sequence is that when you try to sit down and think up an algorithm to solve this problem, you can’t help but think of recursion. The reason for this is because the solution to the next number relies on the past two iterations. Now that’s not to say that the **only** way to solve this problem is with Java recursion, but it can make the coding much simpler.

## The Big Question

So now you know what the Fibonacci sequence is, but here’s the big question: **How do you ‘solve’ this problem with recursion in Java?**

Let’s do it!

There are really only two things any recursive code needs to ensure that it will work properly:

- A defined ending point.
- A constant progression towards that ending point.

So long as you abide by these two rules, you’ll be okay. If you fail to abide by them, you might get caught in an infinite loop and you’ll have to manually terminate your program (not the end of the world).

Well then, what’s the defined “ending point” for our Fibonacci sequence? Well it will come in the form of the problem we wish to solve. The question would be something like this: “What is the 40th number in the Fibonacci sequence?”. So there we have it, that “40th” number is the ending point for our sequence.

Okay, so what’s our constant progression towards that point? It will be that we will need to iterate through our recursion 40 times, one by one. That’s a measurable way of ensuring that we are moving towards the ultimate goal right?

Now with this in mind, let’s think about what the code would look like. The first thing we need to do is think of how the Fibonacci sequence can be represented in terms of an equation. So if the first number plus the second number equals the third… and the second plus the third equals the fourth, then we can describe it like so:

F_{n} = F_{n-1} + F_{n-2}

Make sense? So the _{n} in this case represents the `index`

of any particular number in the sequence. Now obviously, we can’t just plug in the value of 40 for _{n} and know what the answer is, because we need to start back at the very beginning and work our way up to _{n} to figure it out.

Since we need to work our way from the beginning of the equation, then that means we’ll likely need to start there with our coding. So how would our code start then?

public static void main (String[] args) { int n1 = 0; int n2 = 1; System.out.println("n1="+n1); fibonacciSequence(n1, n2); } public static void fibonacciSequence(int n1, int n2) { System.out.println("n2="+n2); }

That seems pretty good as a start, but there’s no recursion going on here… remember we need to call the `fibonacciSequence`

method inside of itself to start Java recursion. The only problem is, if we do this now, it will run forever. Remember the two rules, first we need a clear progression towards an end (F_{n} = F_{n-1} + F_{n-2}) and two we need an end!

So what’s our ending going to be? Well, earlier I arbitrarily chose to go to the 40^{th} index of the equation, so let’s stick with that.

If we are going to be keeping track of which ‘index’ we’re currently ‘at’ then let’s store it as an instance variable. You could also just pass this into the `fibonacciSequence`

method, but I don’t like passing parameters around unless it’s completely necessary. Oh, and we also need to keep track of our ending point, so let’s store that as an instance variable as well.

private static int index = 0; private static int stoppingPoint = 40; public static void main (String[] args) { int n1 = 0; int n2 = 1; System.out.println("n1="+n1); fibonacciSequence(n1, n2); } public static void fibonacciSequence(int n1, int n2) { System.out.println("n2="+n2); }

Okay, so now we’ve established the starting point, the ending point, but not the recursion. So let’s put that in as well:

private static int index = 0; private static int stoppingPoint = 40; public static void main (String[] args) { int n1 = 0; int n2 = 1; System.out.println("index: " + index + " -> " +n1); fibonacciSequence(n1, n2); } public static void fibonacciSequence(int n1, int n2) { System.out.println("index: " + index + " -> " + n2); // make sure we have set an ending point so this Java recursion // doesn't go on forever. if (index == stoppingPoint) return; // make sure we increment our index so we make progress // toward the end. index++; fibonacciSequence(n2, n1+n2); }

And Voila! We have our working algorithm for the Fibonacci sequence.

What’s cool about this sequence is that the numbers grow rapidly after the 40^{th} index. Since we used an `int`

to store our numbers, we will quickly hit the maximum of the `int`

. **Can you tell the index when the results start to show this**? Post it in the comments below.

Also, **can you suggest what we can do to be able to properly display number past the 80**^{th} index? Try it out yourself and post the answer in the comments below if you figure it out.

{ 18 comments… add one }

Nice one again, Trevor!

I’m new to Java, but I have many, many years of programming experience in other languages.

And my experience with recursion taught me the following:

1. Recursion is very useful if the underlying data is recursive, e.g. processing a directory structure or a tree like data structure.

2. Every recursive algorithm can be unfolded to a loop.

3. Never ever test a boundary for equality (especially not if dealing with floating point numbers!) e.g. try to call your myRecursiveMethod(0) or myRecursiveMethod(-1)

4: Only use recursion if the number of calling levels is not too high, because the program stack is limited.

I have converted your fibonacciSequence() from int to BigInteger. Very nice class, btw! I get a StackoverflowError at index 7285, where the generated number is even beyond a double (bitLength()=2678 which equals about 256^335, an abolutely incredible number).

This all said, I would never create recursive code for fibonacci() or factorial().

Hi Trevor!

1:

I think when we start our index=0 then at 40th place index will be 41?

am I true?

Plz Reply…

2:

and how we use swapping in fibonacci series like

value2=value1+value2; and value1=value2;

3:

and in your above code why you never write value1=value2, then how value1 is updated?

Kindly reply me on my email address too …

1) Yes the 40th index will be the 41st iteration (since we start at 0)

2) I don’t understand your question

3) The recursive call to the next iteration of the

`fibonacciSequence`

method has two variables passed into it, it wants`int n1, int n2`

… what do you see me passing in?`n2, n1+n2`

, this is where we properly increment. Here we pass the current value of`n2`

to be our new value of`n1`

in the next iteration, and the new value of`n2`

will be our old values`n1+n2`

.class Fibo

{

static int in=0;

static int st=5;

static int fibo(int i,int j)

{

System.out.print(j);

in++;

if(in<st)

{

return fibo(j,i+j);

}

else

return(i+j);

}

public static void main(String[] args)

{

int a=0,b=1;

System.out.print(a);

System.out.print(fibo(a,b));

}

}

46 is the line where the number becomes larger than the int place holder will allow.

Trevor sir and @robert and @ zulfiqar sir

I am in final year of computer science engineering from india..

M not that good at java m trying to learn it..pls tell me how to proceed to get a good job abroad???

I mean should i cocentrate on java API or on basic programs or what

Pls help meeee

Give ur email id

Learning core Java is probably the most important thing you need to do. From that point, there are a whole bunch of different job opportunities.

If you want to go the same route I did, you should learn about web application programming in Java. This includes:

HTML

CSS

JavaScript

JSPs

Spring Framework

Databases & SQL

With those technologies / languages under your belt, you will be a very well rounded programmer and would be able to get a job abroad so long as you could show that you’ve had real world working experience. Getting real world experience as a programmer is always the toughest part, but it’s a necessary evil for getting employment in North America.

Can you tell the index when the results start to show this?

Ans: when n2 value is lesser then zero we return the index value..

Can you suggest what we can do to be able to properly display number past the 80th index?

Ans: we using long value instead of int.

Thank you so much for posting, I’m a hybrid sysadmin/graphic designer/ui guy/programmer. Until I read this tutorial, I was able to spot cases where recursion was required but unable to implement…. until now! I’m working with Java using the JSF framework, this massively helped me. You get a gold star, Trevor. Thanks so much for posting.

good

In the fibonacciSequence() you ought not to have named the parametric variables as n1 and n2. It does get confusing for beginners as the mistake it for the intial n1 value in main(). We’d best be off with k1,k2 or something. Just a suggestion though

please help in my create a calculater within awt ?

superb

this is very good website

please help me in creating a java recursive prog in which we enter a word and it returns it after removing vowel letters from it

what is the time complexity? Is is O(2^n)?

hello

i want some help if there someone can

it is about how i can make this code with this conditions .

*** write a recursive method that has one parameter, a character, c. This one parameter is one of the characters ‘A’ through ‘Z’. The method will use recursion to print out a pattern of characters as follows:

If the parameter c is the letter ‘A’, then the output will only be ‘A’.

For any other value of c, the output (pattern printed) will have three parts:

1. The output for the previous letter (c -1)

2. Then the letter c will be printed.

3. Then a second copy of the output for the previous letter will be printed.

please if anyone know how to make it please help me .