Results 1 to 3 of 3

Thread: Fabonacci:

  1. #1
    jocdrew21 is offline Senior Member
    Join Date
    Jan 2014
    Posts
    137
    Rep Power
    0

    Default Fabonacci:

    The program runs flawlessly. However my question is about the error I get if I enter a large number like 19,000 but lower ones work fine.

    Java Code:
    Exception in thread "main" java.lang.StackOverflowError
    	at fabonacci.practice.Fabonacci.fabonacci(Fabonacci.java:9)
    	at fabonacci.practice.Fabonacci.fabonacci(Fabonacci.java:16)
    	at fabonacci.practice.Fabonacci.fabonacci(Fabonacci.java:16)
    	at fabonacci.practice.Fabonacci.fabonacci(Fabonacci.java:16)
    	at fabonacci.practice.Fabonacci.fabonacci(Fabonacci.java:16)
    Obviously the overhead the recursive call is making is causing the error. From the the following code:

    Java Code:
    package fabonacci.practice;
    
    import java.util.Scanner;
    
    public class Fabonacci {
    	
    	int fabonacci(int n){
    		
    		if(n==0){
    			return 0;
    		}
    		else if(n==1){
    			return 1;
    		}
    		
    		return fabonacci(n-1) + (n-2);
    			
    	}
    
    	public static void main(String[] args) {
    		Fabonacci f = new Fabonacci();
    		int number;
    		
    		System.out.println("Get your Fabonacci number:");
    		
    		Scanner in = new Scanner(System.in);
    		number = in.nextInt();
    		System.out.println(f.fabonacci(number));
    		
    		in.close();
    
    	}
    
    }
    I am just trying to gather why and understand the language better.

    I did an experiment in C++ to see what happened:
    Java Code:
    #include <iostream>
    
    int fabonacci(int n){
    
        if(n==0){
            return 0;
        }
        else if(n==1){
            return 1;
        }
        
        return fabonacci(n-1) + (n-2);
        
    }
    
    int main(int argc, const char * argv[]) {
        int num;
        
        std::cout<<"Enter a Fabonacci number you want to know\n ";
        std::cin>>num;
        
        int number=fabonacci(num);
        
        std::cout<<number<<std::endl;
        
        return 0;
    }
    Entered the following:
    Java Code:
    Enter a Fabonacci number you want to know
     100000
    704882706
    Last edited by jocdrew21; 12-14-2014 at 04:48 PM.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,423
    Blog Entries
    7
    Rep Power
    27

    Default Re: Fabonacci:

    That number is not the 100000th fibonacci number; the ints overflowed. That aside, the n-th fibonacci number needs stacks of depth n. Better use memoizing or simple iteration.

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  3. #3
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    13

    Default Re: Fabonacci:

    In addition to what Jos said, your recursive algorithm is not correct. You need to return the sum of two fibonacci calls.

    e.g.

    Java Code:
    return fib(n-1) + fib(n-2);
    This increases the stack depth by at least a factor of three for n > 3.

    Edit: And to coin a phrase from a famous movie: "You're going to need a bigger integer." I suggest BigInteger.

    Regards,
    Jim
    Last edited by jim829; 12-14-2014 at 06:04 PM.
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •