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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 7 of 7

Thread: Trying to Find Recursion and Loop Limit

  1. #1
    Member
    Join Date
    Jan 2014
    Posts
    30
    Thanks
    13
    Thanked 0 Times in 0 Posts

    Default 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. #2
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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. #3
    Member
    Join Date
    Jan 2014
    Posts
    30
    Thanks
    13
    Thanked 0 Times in 0 Posts

    Default Re: Trying to Find Recursion and Loop Limit

    Quote Originally Posted by GregBrannon View Post
    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. #4
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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. #5
    Member
    Join Date
    Jan 2014
    Posts
    30
    Thanks
    13
    Thanked 0 Times in 0 Posts

    Default 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. #6
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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. #7
    Member
    Join Date
    Jan 2014
    Posts
    30
    Thanks
    13
    Thanked 0 Times in 0 Posts

    Default 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.
    Last edited by paco; October 5th, 2014 at 11:09 AM.

Similar Threads

  1. Limit Updates
    By Aigyptus in forum Java Theory & Questions
    Replies: 2
    Last Post: August 17th, 2014, 10:54 AM
  2. Trying to find 3 largest numbers in an array using a single For loop
    By javaD1 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 7th, 2014, 10:27 AM
  3. Replies: 5
    Last Post: April 22nd, 2013, 07:27 AM
  4. Loop to find and replace multiple instances of a char
    By Olympaphibian89 in forum Loops & Control Statements
    Replies: 1
    Last Post: October 25th, 2012, 04:11 PM
  5. Unending Loop Issue? Can't find it.
    By computerguy38 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: March 4th, 2011, 08:22 PM