GATE Overflow | Programming | Test 1 | Question: 23

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(int i = 1; i <= x; i++)
    {
        sum += foo(x-i);
    }
    return sum;
}

Answer 1

f(n) = 1, if n=0
f(n) = 2^(n-1), n>=


foo(0) = 1
foo(1) = 1
foo(2) = 2
foo(3) = 4
foo(4) = 8
foo(5) = 16
foo(6) = 32
foo(7) = 64
foo(8) = 128
foo(9) = 256
foo(10) = 512

Comments

How to think in 5 minutes??

---

Best way to solve these kind of problem is to go bottom up. Just check what happens in base condition, then 1 level up.

Example:

f(0) = 1 (base condition)

f(1) = (i=1 to 1, sum = 0 + f(0)) = 1

f(2) = (i=1 to 2, sum = 0 + f(0) + f(1)) = 0+1+2 = 2

f(3) = (i=1 to 3, sum = 0 + f(0) + f(1) + f(2)) = 0 + 1 + 1 + 2 = 4

f(4) = (i=1 to 4, sum = 0 + f(0) + f(1) + f(2) + f(3)) = 0 + 1 + 1 + 2 + 4 = 8

and so on... 

 

---

Adding more to priyesh9875’s comment, think of it as memoization on a paper.

Answer 2

For foo(x), we need foo(x-i). i is positive, hence for any x we'd need to find the values of foo(<less than x>) to obtain foo(x).

It's best to go with a bottom-up approach, and start with foo(0).

• foo(0) = 1
• foo(1) = foo(0) = 1
• foo(2) = Add all previous values = 2.
• foo(3) = Add all previous values = 4
• foo(4) = Add all previous values = 8
• foo(5) = Add all previous values = 16
• foo(6) = Add all previous values = 32
• foo(7) = Add all previous values = 64
• foo(8) = Add all previous values = 128
• foo(9) = Add all previous values = 256
• foo(10) = Add all previous values = 512