CODEWITHSUNDEEP
javarecursionfibonacci
TheNewGuy
TheNewGuy

Reputation: 411

Fibonocci Generation by Recursion

I am trying to create a method that will generate a Fibonacci sequence based on user input and calculated to the tenth number, all through recursion. (Learning recursion right now, this is one exercise).

Here is my attempted code, which I am currently struggling to make work:

//being run with fibonacci(10, 10);
//Start being the number the sequence starts with
public static int fibonacci(int start, int times) 
{
    if(times > 0)
    {
        int result = fibonacci(start - 1, times - 1) + fibonacci(start - 2, times - 1);
        sequence += result;
        return result;
    }
    System.out.println(sequence);
    return start;
}

This, however, returns a large amount (I think about 40,000 numbers taking approximately 10 seconds to run to completion). Also all the numbers appear to be negative, definitely not what my aim was.

Now, on to identifying the problem: I believe the problem is that the method is calling itself twice more every single time it is called, adding up to the large amount. However, I can't think of a way around this seeing as I am trying to do it through recursion each time and I have no choice but to call it again.

As for why it is negative, I haven't a clue. I thought I was using the Fibonacci equation correctly, but obviously I am doing something incorrectly.

Could anyone help me through this please?

(True, I could easily google some code for this as I am sure it is out there, but I want to actually learn how this is done and what I am doing wrong for future reference. Better to advance as a programmer than to get the grade from copied code and move on)

Upvotes: 0

Views: 106

Answers (2)

Sylwester
Sylwester

Reputation: 48745

I think I understand what you are trying to do. You want 10 fibonacci numbers from start. Perhaps something like this will work:

public static int[] fibonacci(int start, int times) 
{
    return fibonacci(start, times, 0, 1, new int[times]);
}

private static int[] fibonacci(int start, int times, int a, int b, int[] answer) 
{    
    if( start > 0 )
        return fibonacci(start-1, times, b, a+b, answer);

    if( times > 0 )
    {
        answer[answer.length - times] = a;
        return fibonacci(start, times-1, b, a+b, answer);
    }

    return answer;
}

public static void main(String[] args) {
    int[] a = fibonacci(5, 10);

    for(int i=0; i<a.length; i++)
    {
        System.out.println(a[i]);
    }
}

Upvotes: 0

user695992
user695992

Reputation:

I think you are a little confused here with what the Fibonacci sequence is. The formula is F(n) = F(n-1) + F(n-2). Recursion should always end at a base case which for Fibonacci is F(0) = 0 and F(1) = 1. Your method only needs one variable which is n.

Think about it this way:

public static int fibonacci(int n) {
  //Insert your base cases here to terminate early
  //Then process the recursive formula
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Upvotes: 2

Related Questions