Question 7-1

[7 pts] Draw a recursion tree representing the recursive calls made to f in the course of computing the value of f(11) using the following method.

public static void f(int n) {
  if(n <= 1) {
    return 1;
  } else if(n % 2 == 0) {
    return 2 * f(n / 2);
  } else {
    return f((n - 1) / 2) + f((n + 1) / 2);
  }
}

Solution

     11
   /    \
  5      6
 / \     |
2   3    3
|  / \  / \
1  1 2  1 2
     |    |
     1    1