Strange behavior in recursive algorithm,

Question

I was writing a recursive algorithm to calculate Fibonacci numbers in Java as part of a programming 101 course. This is the code:

public class Fib {

    public static void main(String[] args) {
        Fib fib = new Fib();
    }

    public Fib() {
        int end = 9;
        long[] nums = new long[2];
        printFib(0, end, nums);
    }

    private void printFib(int i, int end, long[] nums) {
        while(i < end) {
            if(i == 0 || i == 1) {
                nums[i] = 1;
                System.out.println("1");
            } else {
                long fib;
                fib = 0;
                fib += (nums[0] + nums[1]);
                nums[0] = nums[1];
                nums[1] = fib;
                System.out.println(fib);    
            }
            i++;
            printFib(i, end, nums);
        }
    }
}

As I was stepping through the program it was working as intended until i became equal to end, the variable telling the printFib method how many Fibonacci numbers it should print out. When ì was equal to end while(i < 1) returns false as expected and the program go to the last }, now you'd(me) expect the program to return the constructor from which I initially called the function and the program should exit, this not the case. The program goes back to the while statement and somehow evaluates to false again. Then it does the same thing again except the second time it decreases i by 1(what?!) and then proceeds to the else clause when it reaches the if statement. It then does the same thing over and over alternating the amount it subtracts from i between 1 and 2. I've asked my teacher about this and he was unable to explain it.

The program works fully like I intended if I replace the while with an if so maybe there is something about while that I don't know.

Edit So I realize now that each time the method is called i has a different value which is stored and when the method exits and i = end the program goes back to the previous calls where i had a different value.

Eran · Accepted Answer · 2015-02-11 13:41:49Z

4

You implemented an iterative algorithm to calculate Fibonacci series. That's what the while loop does. There is no point in making the recursive call - printFib(i, end, nums) - at the end.

If you intended a recursive implementation, the entire while loop is not needed.

answered Feb 11, 2015 at 13:41

Eran

395k57 gold badges726 silver badges793 bronze badges

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

2 Comments

Reds Over a year ago

Understood. But if I replace the while loop with an if statement would it not be recursive, after all the if statement is only there to make sure that the program does not go on forever. Also, whilst I understand that this is not a recursive implementation of the solution to the problem of finding Fibonnaci numbers, do you have any idea as to why the program behaves the way it does with program going back to the while loop when it shouldn't have(in my mind at least), and why 1 and 2 is subtracted from the variable i?

Eran Over a year ago

@Reds The program goes back to the while loop due to the recursive call. Each recursive call starts a new while loop.

duffymo · Accepted Answer · 2015-02-11 14:12:48Z

This code doesn't look right to me.

I would recommend that you not print from your method. Return a value to the main and let it print.

Your recursive method should not have a while loop in it. That's iteration - exactly what you're trying to avoid here.

Your method should have a stopping condition and a call to itself. That's not what you're doing.

Think about it like this:

/**
 * Recursive Fibonnaci
 * User: mduffy
 * Date: 2/11/2015
 * Time: 8:50 AM
 * @link http://stackoverflow.com/questions/28455798/strange-behavior-in-recursive-algorithm/28455863#28455863
 */
public class Math {

    private static Map<Integer, Integer> memo = new ConcurrentHashMap<Integer, Integer>();

    public static void main(String [] args) {
        for (String arg : args) {
            int n = Integer.valueOf(arg);
            System.out.println(String.format("n: %d fib(n): %d", n, fibonnaci(n)));
        }
    }

    public static int fibonnaci(int n) {
        if (n < 0) throw new IllegalArgumentException("index cannot be negative");
        int value = 0;
        if (memo.containsKey(n)) {
            value = memo.get(n);
        } else {
            if (n <= 1) {                
                value = n;
            } else {
                value = fibonnaci(n-1)+fibonnaci(n-2);
            }
            memo.put(n, value);
        }
        return value;
    }
}

SomeJavaGuy · Accepted Answer · 2015-02-11 13:44:14Z

-1

Basicly this is happening because i would guess that you are thinking of i as an reference which will influence the basic callings of the Fibunacci method calling the sub Fibunacci method. This will finally lead way to many calls of the fibunacci method.

in my eyes the loop doesn´t make sense in your recursive way of solving it.

answered Feb 11, 2015 at 13:44

SomeJavaGuy

7,3872 gold badges24 silver badges33 bronze badges

Collectives™ on Stack Overflow

Strange behavior in recursive algorithm,

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related