For each of the below exercises, first state the base condition. Secondly, perform (without a computer) a full trace showing the levels of recursion.

1. int f(int x)
{
   if (x <= 2) return 1;
   return f(x-1) + f(x-2);
}
Find f(7).

2. int f(int x, int y)
{
   if (y == 0) return x;
   if (x > y) return f(y, x);
   return f(x, y % x);
}
What is an important precondition on x?
   Find f(27,9).
   Find f(45,5).
   Find f(36,17).
   Note: The computer will not trace one and guess at the results of the other two. Therefore, you should not either.

3. int f(int x)
{
   if (x > 5)
      return f(f(x - 2) - 1) + x;
   if (0 < x && x <=5)
      return f(f(x - 1) -2) + 2;
   return x;
}
Find f(9).

4. int f(int x, int y)
{
   if (x <= 0)
      return y;
   if (y <= 0)
      return x;
   if (x > y)
      return f(y -1, x -1) + x*y;
   return f(x, y/2);
}
Find f(4,3).