GATE CS 2011 Q48 — Algorithm Design: Dynamic Programming

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {
    if (n>0) return ((n%r) + foo(n/r, r));
    else return 0;
}

What is the return value of the function $\text{foo}$ when it is called as $\text{foo(345, 10)}$ ?

View worked solution

Answer: B

The function foo(n, r) recursively computes the sum of the digits of the number $n$ when represented in base $r$ .

Let's trace the execution of foo(345, 10) step-by-step:

foo(345, 10): Since $345 > 0$ , it returns (345 % 10) + foo(34, 10) which is $5 + \text{foo}(34, 10)$
foo(34, 10): Since $34 > 0$ , it returns (34 % 10) + foo(3, 10) which is $4 + \text{foo}(3, 10)$
foo(3, 10): Since $3 > 0$ , it returns (3 % 10) + foo(0, 10) which is $3 + \text{foo}(0, 10)$
foo(0, 10): Since $n = 0$ , it returns $0$ .

Substituting the values back, we get:

$\text{foo}(345, 10) = 5 + 4 + 3 + 0 = 12$

Thus, the correct option is B.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions