difficulty with fibonacci function

Question

I'm supposed to change this recursive function, into an iterative function...

int rFib(int n) 
{   //assumes n >= 0
    if(n <= 1)
        return n;
    else
        return (rFib(n-1) + rFib(n-2));
}

But I'm drawing a blank on the mathematical view of this... I would appreciate any assistance. I was able to get the other 3 functions, but I just can't seem to figure out the math of this one.

public static int fib(int n)
{
    int theFib = 1;
    while(n > 1)
    {
        theFib = n - 1;
        n = n + n - 2;         
}
        System.out.println(theFib);
        return theFib;
    }

have a look at javacodegeeks.com/2014/02/dynamic-programming-introduction.html based on dynamic programming — Saravana
– Saravana, Commented Nov 4, 2015 at 2:15
'supposed to change this function'? Is this a homework question? its ok if it is, just be up front about it — jb.
– jb., Commented Nov 4, 2015 at 2:16
for problems like these, i find it really helps to ignore the code completely at first, figure it out on paper or a whiteboard first. then after you know how it works, how would the code look? ie, you have two numbers, you add them together to get a third number, then use that number added to one of your first numbers to get a fourth number. then what happens? when do you stop adding together? — jb.
– jb., Commented Nov 4, 2015 at 2:21
thanks for all the assistance you guys. and yeah, this is hw...I didn't think of having to save the numbers. much appreciated. — L.G
– L.G, Commented Nov 4, 2015 at 19:04

Andreas · Accepted Answer · 2015-11-04 02:22:06Z

1

The next number in the Fibonacci sequence is the sum of the last two numbers, so you'll need to remember the last two numbers.

In pseudo code, since you should do some of the homework yourself:

n1 = 0
n2 = 1
loop
    n = n1 + n2
    n1 = n2
    n2 = n
end loop

I'll leave it to you to limit the looping.

answered Nov 4, 2015 at 2:22

Andreas

160k13 gold badges164 silver badges262 bronze badges

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

Comments

Ely · Accepted Answer · 2015-11-04 02:24:32Z

0

You can find an example here.

The code in question:

public class FibonacciIterative {
    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;
    }
}

It does not really matter which direction (up or down) you count. The challenge is to deal with the limits properly.

answered Nov 4, 2015 at 2:24

Ely

11.2k5 gold badges45 silver badges69 bronze badges

Comments

MNos · Accepted Answer · 2015-11-04 02:33:44Z

0

Using dynamic programming technique:

    static int fib(int n) {
        int[] fibs = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            if (i <= 1) {
                fibs[i] = i;
            } else {
                fibs[i] = fibs[i - 1] + fibs[i - 2];
            }
        }
        return fibs[n];
    }

answered Nov 4, 2015 at 2:33

MNos

5656 silver badges12 bronze badges

Collectives™ on Stack Overflow

difficulty with fibonacci function

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related