845 views

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;
}

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


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 ’s comment, think of it as memoization on a paper.

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

1
500 views
1 vote