# Fibonacci Sequence Using Recursion

Page 1 of 1

## 8 Replies - 6873 Views - Last Post: 20 July 2011 - 05:41 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=240032&amp;s=b5ec2a30131d8ec488df55270f8dde3c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 cheezpwr2

Reputation: 0
• 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.");

Calendar time = Calendar.getInstance();

try {
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

• The Algorithmi

Reputation: 729
• 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.

### #3 Niha

Reputation: 4
• 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!)

### #4 ipushmycar

• D.I.C Regular

Reputation: 86
• 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

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11447
• Posts: 43,145
• 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/

### #6 NeoTifa

• Whorediot

Reputation: 3127
• Posts: 16,587
• 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?

### #7 cheezpwr2

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

## Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 12:37 PM

NeoTifa, 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.

### #8 pbl

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

Reputation: 8365
• Posts: 31,956
• Joined: 06-March 08

## Re: Fibonacci Sequence Using Recursion

Posted 19 July 2011 - 09:34 PM

NeoTifa, 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

### #9 NeoTifa

• Whorediot

Reputation: 3127
• Posts: 16,587
• 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.