1  import java.util.Scanner;

  2  

  3  /**

  4     This program prints trace messages that show how often the

  5     recursive method for computing Fibonacci numbers calls itself.

  6  */ 

  7  public class RecursiveFibTracer

  8  {

  9     public static void main(String[] args)

 10     {  

 11        Scanner in = new Scanner(System.in);

 12        System.out.print("Enter n: ");

 13        int n = in.nextInt();

 14  

 15        long f = fib(n);

 16  

 17        System.out.println("fib(" + n + ") = " + f);

 18     }

 19  

 20     /**

 21        Computes a Fibonacci number.

 22        @param n an integer

 23        @return the nth Fibonacci number

 24     */

 25     public static long fib(int n)

 26     {

 27        System.out.println("Entering fib: n = " + n);

 28        long f;

 29        if (n <= 2) { f = 1; }

 30        else { f = fib(n - 1) + fib(n - 2); }

 31        System.out.println("Exiting fib: n = " + n

 32              + " return value = " + f);

 33        return f;

 34     }

 35  }