2

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

Improve this question
7
  • Yeah sorry, I add that bit there. See I am just confused on this, I am just learning about recursion and not using a for loop to loop my stuff all the time. Commented Apr 18, 2012 at 0:51
  • 2
    Try first writing a recursive multiplication function: int mult(int a, int b). Multiply a times b using only addition on b and subtraction on a, and I think you'll be able to try the Fibonacci sequence. Commented Apr 18, 2012 at 0:51
  • 2
    @user1340054 Your logic is sound, did you try sticking that in a method? Commented Apr 18, 2012 at 0:52
  • Wouldn't even be able to begin on that, I know like if(x<5) run(x+1) and that will give you 1 2 3 4 5, if you print it out. Commented Apr 18, 2012 at 0:55
  • Could you explain that multiplication function to me? Commented Apr 18, 2012 at 0:57

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

What would i be within the fibonacci sequence? It would be the number before it so would it be like n-1?
I'm not quite following what is going on at the return n+sum(i+1,n)
@user1340054: i + sum(i+1, n) (sorry, typo) is adding i to the next recursive call of sum(). In other words, we're iterating through whatever value i is, and adding it to whatever value i+1 will be.
A call chain may look like, if I called it with i=10 and n=12: 10 + sum(11, 12) -> 10 + 11 + sum(12, 12) -> 10 + 11 + 12 -> 33.
so if I did in my main class sum(10,20) that would start i at 10 and then add that until i equals n?
|
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.

Improve this answer

3 Comments

So basically just put what I put at the top into code form and I should be fine? I got 6765 but not the other numbers.
You may need to add some println statements at "choice" locations to print the sequence.
I'm just getting a bunch of random numbers when I try to put in a println statement.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.