Fibonacci Trace

Question

I just want to be upfront that this is a homework assignment. I have attempted the problem in so many different ways that I am just out of ideas for why I am not getting the desired output.

Problem

Write a program that will trace how Fibonacci numbers are generated recursively (for any N) and display the trace in the following way :

Example (N=4):

Entering level 0
Entering level 2
Entering level 4
Exiting level 4
Entering level 3
Exiting level 3
Exiting level 2
Entering level 1
Entering level 3
Exiting level 3
Entering level 2
Entering level 4
Exiting level 4
Entering level 3
Exiting level 3
Exiting level 2
Exiting level 1
Exiting level 0

---

My Main:

public class A5main {

public static void main(String[] args) {
    //n holds user input
    //level is the current level of the tree
    //fibonacci is a5class object
    int n;
    int level=0;
    a5class fibonacci= new a5class();
    Scanner keyboard = new Scanner(System.in);

    //Ask user for input

   System.out.println("Enter a number up to which Fibonacci series to print: ");
   n = keyboard.nextInt();
   System.out.println("Fibonacci trace of: " + n);

    //Pass input to fibonacci.trace method with arguments n, level.
   fibonacci.trace(n,level);

}
}

My class:

 package a5main;
 public class a5class {
    int fibWork;
   public a5class()     
{ 
}
public int trace(int t, int level)
{
    //Accepts t and level as an argument.
    //Lets uer know what level they are entering 
    System.out.println("Now entering level " + level);
    //If t<=1 just return the value
        if (t<=1)
        {
            System.out.println ("\tNow exiting level " + level);
            return t;

        }
        //Else use recurssion to figure out the fibonacci sequence
        //and determine what level you are on.
        else
        {
            fibWork = trace(t-1, level+1) + trace(t-2, level+1);
            System.out.println ("\tNow exiting level " + level);
            return t; 
        }
}
}

(I put the \t there so I can see where it is exiting easier for now)

My Output:

Enter a number up to which Fibonacci series to print: 
4
Fibonacci trace of: 4
Now entering level 0
Now entering level 1
Now entering level 2
Now entering level 3
     Now exiting level 3
Now entering level 3
     Now exiting level 3
     Now exiting level 2
Now entering level 2
     Now exiting level 2
     Now exiting level 1
Now entering level 1
Now entering level 2
     Now exiting level 2
Now entering level 2
     Now exiting level 2
     Now exiting level 1
     Now exiting level 0

I've also attempted to not pass 'level into the method and have it equal 0 in my public a5class when the object is created but have had no luck with it so far.

While mine might not be so far off I notice that it exits level 3 and then re-enters it in the next sequence which doesn't seem logically correct either.

I appreciate any help or guidance. Even just a pointer in the right direction is appreciated. I take my programming seriously and want to actually comprehend it. I don't want to 'fake' my way through it and have a worthless degree.

Thank you!

Answer 1

From the expected output you'll see that the program expects to enter level 2 directly from level 0, and level 4 from level 2. That can only happen if you add 2 to the level in first recursive call:

fibWork = trace(t-2, level+2) + trace(t-1, level+1);