Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Trying to Find Recursion and Loop Limit

1. ## Trying to Find Recursion and Loop Limit

hello, I am doing some code on calculating the fibonacci sequence in 2 different methods, one is through recursion and the other is through a for loop. And so, I am trying to figure out the max value or limit for each of these methods where the function/method does not result in stack overflow, and I am not sure how to go about this, here is my code so far:

```import java.util.Scanner;
public class Recursion {

public static void main(String[] args)
{
Scanner kb = new Scanner(System.in);
long n, result1, result2, startTime1, stopTime1, startTime2, stopTime2;

System.out.println("Please Enter A Number in between 0 and maxValue, will be calcualtred using 2 methods....");
n = kb.nextLong();

startTime1 = System.nanoTime();
result1 = fibRecursive(n);
stopTime1 = System.nanoTime();

startTime2 = System.nanoTime();
result2 = fibLoop(n);
stopTime2 = System.nanoTime();

System.out.println("\nDisplaying solution for recursive method "+ result1 + "Time Taken: " + (stopTime1 - startTime1));
System.out.println("\nDisplaying solution for loop method "+ result2 + "Time Taken: " + (stopTime2 - startTime2));
System.out.println("\nThanks for using our fibnoacci calculator. ");
}

public static long fibRecursive(long i)
{
if(i == 0)
return 0;
else if(i == 1)
return 1;
else
return fibRecursive(i - 1) + fibRecursive(i - 2);
}
public static long fibLoop(long k)
{
long a = 0, b = 1, ans = 0;
for(int i = 1; i < k; i++)
{
ans = a + b;
a = b;
b = ans;
}
return ans;

}

}```

is there perhaps a built in function/feature in java to determine this number? In my case I am looking for the max value for "long n". Any help is great appreciated, thanks.

2. ## Re: Trying to Find Recursion and Loop Limit

I think you're wondering what's the largest number in the Fibonacci series using either a recursive or iterative algorithm. The possible bounds are the largest long value and the number of times the recursive method can be called before the stack overflows.

You can find the range of long values in Java by Googling. You can verify what you read by writing a simple program to count past the upper range, printing the values as it counts.

You can find how many times a recursive algorithm can recurse on your system by writing a simple recursive method that prints an incrementing number each time through the method. From that you can determine the last Fibonacci term possible on your system as it's currently configured. The size of the stack can be changed, so that's an adjustable boundary.

3. ## Re: Trying to Find Recursion and Loop Limit

Originally Posted by GregBrannon
I think you're wondering what's the largest number in the Fibonacci series using either a recursive or iterative algorithm. The possible bounds are the largest long value and the number of times the recursive method can be called before the stack overflows.

You can find the range of long values in Java by Googling. You can verify what you read by writing a simple program to count past the upper range, printing the values as it counts.

You can find how many times a recursive algorithm can recurse on your system by writing a simple recursive method that prints an incrementing number each time through the method. From that you can determine the last Fibonacci term possible on your system as it's currently configured. The size of the stack can be changed, so that's an adjustable boundary.
Yes you are right, I am looking for the largest number in the Fibonacci sequence that will result in stackOverFlow. If I input a very large number though I don't actually get stack-overflow, eclipse simply lags and never outputs an answer(so how would I even print numbers). Ive looked around but still cant quite figure this out, through google i saw this:

```try {

} catch(StackOverflowError e){
System.err.println("ouch!");
}```

but I am having problems implementing this and dont fully grasp its concept.

4. ## Re: Trying to Find Recursion and Loop Limit

I was thinking of a method like:
```    private static void causeStackOverflowAndCount( int count )
{
System.out.println( count++ );
causeStackOverflowAndCount( count );
}```
When I run it on my computer, I get a StackOverflowError after counting to 10,816. From that, one might conclude that the largest Fibonacci number that could be achieved on my computer is the 10,816 term. You should be able to find the value of that term - or the right one on your computer - and then determine if that value is larger than the largest Long.

5. ## The Following User Says Thank You to GregBrannon For This Useful Post:

paco (October 4th, 2014)

6. ## Re: Trying to Find Recursion and Loop Limit

I still do not understand what you are doing, how would I call on that method and would I use it for both or just the recursive method? Also, how did you get 10816? If I input the fibonacci number of 21 I will get 10946. The long number is java is 2^64 , so I'm guessing thats my limit? Also, if I input a large number into my above code, lets say '100', I never attain stack overflow, my computer simply never calculates the values and nothing ever shows. Thanks for your help so far.

7. ## Re: Trying to Find Recursion and Loop Limit

I still do not understand what you are doing, how would I call on that method and would I use it for both or just the recursive method? Also, how did you get 10816?
Okay, back up.

Your question was, "What is the largest Fibonacci number that can be calculated using a recursive method before a StackOverflowException occurs?"

I suggested that one way to determine that would be to create a simple recursive method that simply counted and displayed the count each pass through the method until the StackOverflowException occurred. The stack size is variable and may not be the same on every person's computer, but the number of passes through the counting recursive method would show how many terms of the Fibonacci sequence could be calculated before an exception occurred.

So I ran that method on my computer and got an exception after 10,816 passes through the method. That means I could calculate the 10,816th term of the Fibonacci series. There's a way to find out what that number is. However, if the 10,816th term of the Fibonacci series is greater than the max Long value, and a Long value is being used to store each term of the Fibonacci series in the recursive method, then the max Long value will decide the limit, not the stack size.

8. ## Re: Trying to Find Recursion and Loop Limit

I dont understand how I would use the method you gave me to keep it continuously counting until stackoverflow occurs. Would I call on it as soon as I call on my 2 other methods?

UPDATE: Also if its the user who is inputting the number how would the user know what the limit is? Sorry for all the questions but still this is baffling to me.