SSelf

Question

The value returned by the following function for foo(10) is ____

int foo(int x)
{
    if(x < 1)
        return 1;
    int sum = 0;
    for(i = 1; i <= x; i++)
    {
        sum += foo(x-i);
    }
    return sum;
}

Comments

Is answer 512??

---

Yes

Debashish Deka Expalined it .

If you want to add some more points then please .

Answer 1

With the help of recursion tree we can easily find the function value for some small numbers.

$\begin{align*} &\text{foo}(0) = 1 \\ &\text{foo}(1) = 1 \\ &\text{foo}(2) = 2 \\ &\text{foo}(3) = 4 \\ &\text{foo}(4) = 8 \\ &\text{foo}(5) = 16 \\ &\text{foo}(6) = 32 \\ \end{align*}$

We can see that, for $n > 0$ $ \;\;\;\; \text{foo}(n) = 2^{n-1} $

Therefore $\text{foo}(10) = 512$