001package algs11; 002 003import stdlib.StdOut; 004 005public class MyRecursionTrace { 006 007 public static int fib(int n) { 008 if (n <= 1) return n; 009 int nMinus1 = fib(n-1); 010 int nMinus2 = fib(n-2); 011 return nMinus1 + nMinus2; 012 } 013 014 public static int gcd(int p, int q) { 015 StdOut.println("gcd(" + p + "," + q + ")"); 016 if (q == 0) return p; 017 int r = p % q; 018 return gcd(q, r); 019 } 020 021 public static void doSomething(int n) { 022 if(n <= 1) { 023 StdOut.print(n); 024 } else if(n > 3) { 025 StdOut.print(n); 026 doSomething(n/2); 027 StdOut.print(n); 028 } else { 029 StdOut.print(n); 030 doSomething(n-1); 031 doSomething(n-2); 032 StdOut.print(n); 033 } 034 } 035 036 public static void main(String[] args) { 037 int f = fib(4); 038 StdOut.format("f=%s\n", f); 039 040 int g = gcd(9, 24); 041 StdOut.format("g=%s\n", g); 042 043 doSomething(7); 044 } 045}