8 Replies - 3945 Views - Last Post: 20 July 2011 - 05:41 AM Rate Topic: -----

#1 cheezpwr2  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-July 11

Fibonacci Sequence Using Recursion

Posted 18 July 2011 - 07:00 PM

Hey guys, I'm having a bit of a problem integrating the Fibonacci recursion code into my previous code that catches exceptions. This is my exception code
import java.io.*;
import java.util.*;
import java.math.*;
import java.text.*;


public class Fibonacci {

	public static long fibonacci(long number){
		
		System.out.println("Please enter how many numbers of the Fibonacci Sequence you would like.");
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Calendar time = Calendar.getInstance();
		
		
		try {
		      String input = br.readLine();
		      int n = Integer.valueOf(input).intValue();
		      fibonacci(n);
		    } catch (NumberFormatException e){
		      System.out.println("Don't be silly, that is not an integer!");
		    } catch (IOException e) {
		      System.out.println("ENTER SOMETHING.");
		    }
		return number;
	}
}



and this is my recursion code
public class Fibonacci_1 {
	public static int fib(int n) {
                int prev1=0, prev2=1;
                for(int i=0; i<n; i++) {
                    int savePrev1 = prev1;
                    prev1 = prev2;
                    prev2 = savePrev1 + prev2;
                }
                return prev1;
	}

        public static void main(String[] args) {
	    for (int i=0; i<=46; i++)
	        System.out.println(fib(i)+", ");
	}

}



How do I integrate the recursion inside?

Is This A Good Question/Topic? 0
  • +

Replies To: Fibonacci Sequence Using Recursion

#2 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 726
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 05:12 AM

hmm I don't see any recursion here.
Was This Post Helpful? 0
  • +
  • -

#3 Niha  Icon User is offline

  • New D.I.C Head

Reputation: 4
  • View blog
  • Posts: 42
  • Joined: 20-April 07

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 05:50 AM

The code you've shown doesn't implement recursion. Recursion means calling the same function again and again to reduce the complexity of the problem solved in each step until you ultimately reach a problem so small that you can solve it (base case). Here the base case is the fact that the first two numbers of the Fibonacci sequence are 1 and 1. Here's a working code for this function (recursion for fibonacci)

int fib(int n)
    {
        if(n == 1 || n == 2)
        return 1;
        else 
        return(fib(n - 1) + fib(n - 2));
    }



Another problem I noticed with your code is that you're calling the same method fibonacci again in itself but this is not the function that computes the Fibonacci number but the one that asks the user for the number upto which Fibonacci numbers have to be computed.

Also, it would be wise to define both methods in the same class, else be sure to include the class name too while calling the method

By the by, recursion is not a very effective method for computing Fibonacci numbers as it calculates the same number multiple times. I read somewhere about a very efficient technique called memoization.

(My explanations may not be fully accurate as I am just a student!)
Was This Post Helpful? 0
  • +
  • -

#4 ipushmycar  Icon User is offline

  • D.I.C Regular

Reputation: 86
  • View blog
  • Posts: 390
  • Joined: 29-August 10

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 06:07 AM

macosxnerd101, has a good tut on how to use recursion you should look at it.

EDIT: It can be found, Here

This post has been edited by ipushmycar: 19 July 2011 - 06:10 AM

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10194
  • View blog
  • Posts: 37,646
  • Joined: 27-December 08

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 08:31 AM

Nina is correct. Recursion isn't the most effective way of finding the nth Fibonacci number. You can optimize the recursion with memorization using a Map to store already calculated Fibonacci numbers. Solving the recurrence will allow you to find the nth Fibonacci number in O(1) time. Check out my links:
http://www.dreaminco...snippet6172.htm
http://www.dreaminco...tial-equations/
Was This Post Helpful? 1
  • +
  • -

#6 NeoTifa  Icon User is offline

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,469
  • Joined: 24-September 08

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 09:18 AM

The question has already been answered, but what I wanna know is:

Calendar time = Calendar.getInstance(); 


wat?
Was This Post Helpful? 0
  • +
  • -

#7 cheezpwr2  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 09-July 11

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 12:37 PM

View PostNeoTifa, on 19 July 2011 - 09:18 AM, said:

The question has already been answered, but what I wanna know is:

Calendar time = Calendar.getInstance(); 


wat?




I'm also trying to use the calendar class to show the time elapsed.
Was This Post Helpful? 0
  • +
  • -

#8 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8316
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 09:34 PM

View PostNeoTifa, on 19 July 2011 - 12:18 PM, said:

The question has already been answered, but what I wanna know is:

Calendar time = Calendar.getInstance(); 


wat?

Usually no need to have 100 occurence of the Calendar class in your code
This is the way you only get one shared by all methods who require it :^:
Was This Post Helpful? 0
  • +
  • -

#9 NeoTifa  Icon User is offline

  • Whorediot
  • member icon





Reputation: 2498
  • View blog
  • Posts: 15,469
  • Joined: 24-September 08

Re: Fibonacci Sequence Using Recursion

Posted 20 July 2011 - 05:41 AM

Oh, I didn't see it implemeted or printd, so I was confused.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1