×

# Foo function

Recently I took the test for Computer Science and I got a Level 3... I couldn't figure out the Level 4 Question and I found it quite interesting and could anyone explain me how it works..?

How many '1' s are printed out when you call foo(5)?

   # python code start
def foo(n):
count = 1
if n > 0:
count += foo(n - 1) + foo(n - 1)
print '1'
return count


Note by Muzaffar Ahmed
3 years, 3 months ago

Sort by:

the answer is exactly 28 · 2 years, 8 months ago

Have you tried doing it for $$n=1$$ and $$n=2$$? Staff · 3 years, 3 months ago

Nope.. I'm not so good at programming so can you please explain me this one from the beginning..? · 3 years, 3 months ago

If you call foo(1), it is greater than zero and, so, the function passes the if statement. It the adds 2*foo(0) (which needs to be called) to count and prints 1.

When it calls foo(0), 0 is not greater than 0 and, so, the if statement is not passed. The function then runs the code that appears after the if statement, where it returns the current value of count which is 1 and prints 1. However, foo(0) was called twice (count += foo(0) + foo(0)), so it prints 1 twice.

So, for foo(1), we print 1 a total three times.

If we called foo(2), this same kind of branching process would occur. I.e., we'd print 1, then we'd call foo(1) twice, which would print 1 twice, then for each foo(1), we'd call foo(0) twice (a total of 4 foo(0)) calls, which would print 1 four times. Making a total of 7. In general, calling foo(n), we print 1 a total of $$2^{n+1}-1$$ times. Staff · 3 years, 3 months ago

Ohh.. I got it.. ! Thanks bro :-) · 3 years, 3 months ago

No problem. It was foon to explain. Staff · 3 years, 3 months ago

Lol :D · 3 years, 3 months ago

:) There's a trick. · 3 years, 3 months ago