Java Recursion basics

For those who don’t know what recursion is (and like a good laugh), click on this link: Google search: Recursion and click on the “did you mean…” item.

Hopefully you’ve finally figured out that recursion is anything that refers to itself (if not, then you may be stuck browsing google forever trying to find out what recursion is!). A fairly common example of recursion is the Fibonacci numbers. The pattern for Fibonacci numbers is to add the 2 previous terms together for the next term, starting with one and one.

Below is the recurrence relationship for Fibonacci numbers:

F(1) = F(2) = 1
F(n) = F(n-1)+F(n-2)

A recurrence relationship is any relationship where the original function refers to itself. So how do we find F(5)?

F(5) = F(4) + F(3)
F(5) = [F(3)+F(2)] + [F(2)+F(1)]
F(5) = [F(2)+F(1)] + 1 + 1 + 1
F(5) = 1+1+1+1+1
F(5) = 5

Seem like a lot of work? Well, to the computer it’s fairly fast most of the time. Later on, I’ll tell you about Dynamic Programming so we can speed this up when you want to compute large Fibonacci numbers.

So what are all the parts of a recursive function? First of all, what is a recursive function? A recursive function is any function that calls itself (either directly or indirectly). Here’s a simple example in Java:

public static void doIt()
{
    doIt();
}

Of course, this will eventually cause a stack-over flow error, so it’s not recommended you try this code for real.

All useful recursive functions have this general property: reduce the problem until it’s so easy the computer can solve it. To fulfill this, recursive functions must have:

  1. Base cases defined (cases where the solution is obvious, and can’t be reduced any further)
  2. Reduction step (place to simplify the given problem)
  3. Recursion call to itself (basically solve the simpler case)

In the Fibonacci recursive function above, you can see that it was recursing until it was just adding up 1’s. This is because in the Fibonacci sequence 1 is the base case, so we just had to add up 1 some number of times to get F(n).

In theory, all recursive functions can be written iteratively, and all iterative functions can be written recursively. However, in practice you’ll find that one or the other of these philosophies will work better depending on the case.

Let’s look at the Factorial function recursively, and compare it to its iterative relatives.

Factorial(N) = 1*2*3*…*N
Basically, multiply all the integers from 1 to N to get the factorial of N.

Implemented iteratively, your code would look something like this:

public static int iterativeFactorial(int n)
{
     int answer = 1;
     for (int i = 1; i < n; i++)
     {
          answer *= i;
     }
     return answer;
}

We can also write the recursive equivalent of this function: F(1) = 1 F(N) = F(N-1)*N can you see how this would yield the same results as the iterative factorial? Here’s the code to compute factorials recursively:

public static int recursiveFactorial(int n)
{
     if (n == 1)
     {
          return 1;
     }
     else
     {
          return n * recursiveFactorial(n-1);
     }
}

So, in terms of performance, how does recursion stack up against the iterative solution here? Sadly, the answer is quite poorly. Recursive function here requires lots of memory to store the method stack and keep track of all the variables in each recursive call, while iterative solutions only have to keep track of the current state. So why even bother with recursion? Because many times when recursion is used correctly it’s performance can out-strip that of iterative solutions, and recursive functions can also be easier to write (sometimes).

Dynamic Programming

Dynamic programming is a form of recursion, but it’s implemented iteratively. Remember our Fibonacci computer above? F(5) = F(2) + F(1) + F(2) + F(2)+F(1) F(5) = 3 * F(2) + 2 * F(1) We have quite a few “over-computations” here. It was only necessary to compute F(2) once, and F(1) once. In this case, it wasn’t too computationally tasking to compute these few terms, but there will be some situations where it will become almost impossible to recompute the solutions hundreds of times. So instead of re-computing, we store the answer away.

public static int dynamicFibonacci(int n)
{
     int[] prevSolutions = new int[n];
     if (n == 1 || n == 2)
     {
          return 1;
     }
     prevSolutions[0] = 1;
     prevSolutions[1] = 1;
     for (int i = 2; i < prevSolutions.length; i++)
     {
          prevSolutions[i] = prevSolutions[i-1] + prevSolutions[i-2];
     }
     return prevSolutions[n-1];
}

So, take F(5) again. If we did it the recursive way, it would have been 8 calls to recursiveFibonacci. However, here we only computed F(1),F(2),F(3),F(4), and F(5) once. This gain of 3 less calls may not seem like much, but what if we tried computing F(50)? dynamicFibonacci will only compute 50 numbers, but recursiveFibonacci could take over 1000 (of course, I haven’t counted so I don’t know if it’s over 1000 or not).

The last note on dynamic programming is that it only helps in cases were we have tons of over-lap. Remember the recursiveFactorial function? If we called recursiveFactorial(50) and dynamicFactorial(50), they will take roughly the same time to run because we’re making the same number of computations. This is because there’s no over-lap what-so ever. This is also why sorting algorithms are a poor choice to implement with dynamic programming: if you analyze most sorting algorithms, they have almost no overlapping solutions, thus is a poor candidate for dynamic programming.

Here are some questions about recursion and dynamic programming:

  1. Implement the recursiveFactorial method (and you thought I had forgotten to put this in there)
  2. For the given recursive relationship, write a recursive method that will find F(N)
  3. What does this recursive relationship mean in iterative terms? Write an iterative solution to this problem.
  4. Is this recursive relationship a good candidate for dynamic programming? Why/why not?
  5. Is there a better way to solve this problem than the iterative or recursive solutions? What is it (if there is one)? Hint: think of Carl Gauss

For problems 2-5, use this recursive relationship:
F(1) = 1
F(N) = F(N-1) + N

Answers are to come…

Reference: Recursion from our JCG partners at the Java Programming Forums

Related Articles :

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

One Response to "Java Recursion basics"

  1. ebrahimi says:

    I want Indirect source code indirect recursion in java please help me
    who can help me?

Leave a Reply


nine − 2 =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close