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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewest:) There's a trick.

Log in to reply

So tell me please :) I know we can directly execute it but I want to understand how it works..

Log in to reply

Have you tried doing it for \(n=1\) and \(n=2\)?

Log in to reply

Nope.. I'm not so good at programming so can you please explain me this one from the beginning..?

Log in to reply

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.Log in to reply

Log in to reply

`foo`

n to explain.Log in to reply

Log in to reply

the answer is exactly 28

Log in to reply