Finding the numbers in the Fibonacci sequence using recursion

Question

Basically, I am looking to write a program that will give me the sequence but up to a certain number. So let's say I want to go up to the 20th number or something. I would like to know how to iterate it recursively so that it finds the values of each number in the sequence up to that number simply by using an if() statement. I don't have any code because all I know is how to do it with a for loop, which isn't the approach I need.

I know this much at least:

if n = 1 || n = 0
   return n;
else 
    return F(n-1) + F(n-2);

Code:

class Fibonocci {

    public static int factorial(int i,int n) { 
        System.out.println(i);

        if(i==n || n==0 || n==1) {  // base case;  when i = n, we're done.
            return n; 
        } else {
            return i + 1 + factorial(i+2,n); // iterative case; we're still adding values up.
        }
    }

    public static void main(String[] args)
    {
        Fibonocci test= new Fibonocci();
        System.out.println( test.factorial(0,10) );
    }
}

I have been trying that and a whole bunch of other tries but I am still stumped. I know it goes 0 1 1 2 3 5 8 13 21 34...

Answer 1

You'd be surprised, but you're pretty much there with your code. My feeling is that you're not comfortable with recursion yet.

Anything you can do iteratively can be done recursively.

Think of it like this: A loop (for, while, do-while) has an iterative step, and a condition to check to see if it's complete. For instance, if I was adding all numbers from 1 to n:

int sum = 0;
for(int i = 1; i <= n; i++) { // Condition to check completion
    sum += i;  // iterative step
}

To convert this to a recursive function, I require a condition for completion - called a base case - and an iterative step, or iterative case. For the summation, my base case would be either when i==n.

public int sum(int i, int n) {
    if(i == n) {  // base case;  when i = n, we're done.
        return n; 
    } else {
        return i + sum(i+1, n); // iterative case; we're still adding values up.
    }
}

Apply this to your Fibonacci method, and I think that you'll be just fine. No really, wrap it in a function call with the appropriate arguments, and you'll be fine.

---

Further Clarification: How Are the Calls Expanded?

Going back to the summation method, let's say that I want to sum the numbers between 1 and 10. How are the calls expanded?

Iteratively

Not much doin' on the call stack, really. It's going through a loop. However, we can synthesize what is going on every time through.

int sum = 0;
for(int i = 1; i <= 10; i++) {
    sum += i;
}

What this looks like through the loop:

Cycle #1: sum=1
Cycle #2: sum=3
Cycle #3: sum=6
Cycle #4: sum=10
Cycle #5: sum=15
Cycle #6: sum=21
Cycle #7: sum=28
Cycle #8: sum=36
Cycle #9: sum=45
Cycle #10: sum=55
Sum = 55

Seems right so far.

We are merely taking one element every time and adding it to a collective summation value. In essence, 1+2+3+4+5+6+7+8+9+10 gets broken down into the following manner:

sum += 1 // 1 now
sum += 2 // 3 now
sum += 3 // 6 now
...
sum += 10 // 55 now

Recursively, there isn't any difference in how the values are gathered, but it's done slightly differently.

Recursively

Examine the calls for this:

public int sum(int i, int n) {
    return n == i ? n : i + sum(i+1, n); // ternary if-else statement, the exact same as the if-else in the above sum method.
}

1 + sum(2, 10)
1 + 2 + sum(3, 10)
1 + 2 + 3 + sum(4, 10)
1 + 2 + 3 + 4 + sum(5, 10)
1 + 2 + 3 + 4 + 5 + sum(6, 10)
1 + 2 + 3 + 4 + 5 + 6 + sum(7, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + sum(8, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + sum(9, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + sum(10, 10)
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
55

It's doing, essentially, the same thing in the recursive call as it would in the serial call. The expansion is a bit funny, but once you get used to it, it won't be a challenge.

From here, I strongly encourage you to try it out. Don't be afraid to experiment; the information that's provided here is plenty sufficient to get you started.

Answer 2

Let me help you by writing a recursive factorial function :

The factorial method is defined as:

 if n == 0 || n == 1 return 1; else return n * F(n - 1);

which can be written in Java as:

public int factorial(int n) { 
   if(n == 0 || n == 1) { 
       return 1;
   } else { 
       return n * factorial(n - 1);
   }
}

So I think thats plenty for you to adapt and test for the fibonacci sequence given what you know.