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}