Thread: 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.

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.

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.

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.

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.

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.