Consider the following code.
public static int recur3(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return recur3(n - 1) + recur3(n - 2) + recur3(n - 3);
}
What value would be returned if this method were called and passed a value of 5?
3
9
11
16
Should be 9
To determine the value that would be returned if the method is called with a value of 5, we need to trace the execution of the recursion.
In this method, we have a base case for values 0, 1, and 2. For any other value of n, we calculate the value by recursively calling the method with n-1, n-2, and n-3 and summing the results.
Let's go step by step:
recur3(5) = recur3(4) + recur3(3) + recur3(2)
= (recur3(3) + recur3(2) + recur3(1)) + (recur3(2) + recur3(1) + recur3(0)) + 2
= ((recur3(2) + recur3(1) + recur3(0)) + recur3(1) + recur3(0) + 1) + (recur3(1) + recur3(0) + 1) + 2
= (((recur3(1) + recur3(0) + recur3(0)) + 1 + 0 + 1) + 1 + 0 + 1) + (1 + 0 + 1) + 2
= (((1 + 0 + 0) + 1 + 0 + 1) + 1 + 0 + 1) + (1 + 0 + 1) + 2
= ((1 + 0 + 1 + 1 + 1) + 1 + 1) + 2
= 6 + 2
= 8
Therefore, if the method is called with a value of 5, it will return 8.
from the last statement,
r(5) = r(4)+r(3)+r(2)
r(4) = r(3)+r(2)+r(1)
r(3) = r(2)+r(1)+r(0)
So do the math