``` 01 02 03 04 05 06 ``` ``` public static int g (int n) { if (n <= 1) return n; int nMinus1 = g (n-1); int nMinus2 = g (n-2); return nMinus1 + nMinus2; }```

Bottom up (from the base case):

```  g(0) = 0
g(1) = 1
g(2) = g(0) + g(1) =  0 +  1 =  1
g(3) = g(1) + g(2) =  1 +  1 =  2
g(4) = g(2) + g(3) =  1 +  2 =  3
g(5) = g(3) + g(4) =  2 +  3 =  5
g(6) = g(4) + g(5) =  3 +  5 =  8
g(7) = g(5) + g(6) =  5 +  8 = 13
g(8) = g(6) + g(7) =  8 + 13 = 21
g(9) = g(7) + g(8) = 13 + 21 = 34
```

Top down (from the initial argument):

```  g(5) = g(3)                   + g(4)
= (g(2)          + g(1)) + g(4)
= ((g(0) + g(1)) + g(1)) + g(4)
= ((0    + 1   ) + 1   ) + g(4)
= 2                      + g(4)
= 2                      + g(3)                   + g(2)
= 2                      + (g(2)          + g(1)) + g(2)
= 2                      + ((g(0) + g(1)) + g(1)) + g(2)
= 2                      + ((0    + 1   ) + 1   ) + g(2)
= 2                      + 2                      + g(2)
= 2                      + 2                      + (g(0) + g(1))
= 2                      + 2                      + (0    + 1   )
= 2                      + 2                      + 1
= 5```

You can view this as a call tree:

```    g(5)
+ g(4)
|   + g(3)
|   |   + g(2)
|   |   |   + g(1)
|   |   |   + g(0)
|   |   + g(1)
|   + g(2)
|       + g(1)
|       + g(0)
+ g(3)
+ g(2)
|   + g(1)
|   + g(0)
+ g(1)
```
• `g(5)` calls `g(4)` and `g(3)`.
• `g(4)` calls `g(3)` and `g(2)`.
• etc.