CSC300 / CSC402: Reading pure recursive functions [12/14]

Another example:

  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):
Building up a table
Memoizing

  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.