      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  }