Programming Basics (Pseudocode Tracing)
When the following function c is called as c(4, 2), how many times is c called, including the first call?
○integer: c(integer: n, integer: k)
if (k = 0 or k = n)
return 1
endif
return c(n − 1, k − 1) + c(n − 1, k)- A5
- B6
- C11
Show answer and explanation
Answer: C. 11
c(n, k) computes the number of ways to choose k items from n (the binomial coefficient) using the Pascal's triangle relation. c(4, 2) calls c(3, 1) and c(3, 2); these call c(2, 0) and c(2, 1), and c(2, 1) and c(2, 2); each of the two c(2, 1) calls makes calls to c(1, 0) and c(1, 1). There are 6 calls that return 1 and 5 calls that make two further calls, 11 in total. The return value is 6, equal to the number of calls that return 1.
- A. This counts only the calls that make two further calls. The 6 calls that return 1 also count.
- B. This is the return value c(4, 2) = 6, not the number of calls.
- C. Correct. The 6 calls that return 1 plus the 5 that make two further calls.
Continue: 9 more Programming Basics (Pseudocode Tracing) questions