Review for Quiz 7

Question 7-1

Consider the following recursive class method. 

public static void printStuff(int n) {
    if(n > 0) {
        printStuff(n - 1);
        IO.println(n);
        printStuff(n - 2);
    }
}
Suppose a program called printStuff(4). What would the computer print?

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).

Solutions

Solution 7-1

1
2
3
1
4
1
2

Solution 7-2

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