Question 7-2

Consider the following recursive class method.

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

Draw the recursion tree illustrating how this function would compute f(5).

Solution

          5
        /   \
      4       2
     / \     / \
   3     2   1 1
  / \   / \
 2   1  1 1
/ \
1 1