in Programming
845 views
6 votes
6 votes

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;
}
in Programming
by
845 views

2 Answers

6 votes
6 votes
Best answer
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
selected by

4 Comments

How to think in 5 minutes??
0
0

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... 

 

2
2

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

0
0
0 votes
0 votes

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
Answer:

Related questions