Python Function Return Loop

Question

Ok, so this piece of code is from a practice question at my school. We are to mentally parse the code and check the answer.

When I first parsed it, I got 4. I copied the code and ran it through IDLE and got 8. I ran the debugger and saw that the else: return is looping the if else statement until x == 0 and then it returns 1.

I do not understand how return 1 is coming out to 8.

def foo(x=5):
    if x == 0:
        return 1
    else:
        return 2*foo(x-1)

print(foo(3))

I understand that it is calling foo(x-1) inside the function foo(x=5) which makes it check if else again and again until x == 0 then it returns 1. How does return 1 end up printing 8?

Answer 1

You will make following calls to foo:

foo(3) -> foo(2) -> foo(1) -> foo(0)

those will return

foo(0) -> 1
foo(1) -> 2 * foo(0) -> 2 * 1 -> 2
foo(2) -> 2 * foo(1) -> 2 * 2 -> 4
foo(3) -> 2 * foo(2) -> 2 * 4 -> 8

Is it clear now?

Answer 2

I think you’re having the right idea (otherwise you wouldn’t have gotten the answer 4), you’re simply aborting too early in your mental exercise.

You can keep track of the variables by tabulating them while going through the code:

• foo(3)
  • calls foo(3 - 1) → foo(2)
    • calls foo(2 - 1) → foo(1)
      • calls foo(1 - 1) → foo(0)
        • returns 1
      • returns 2 * foo(1 - 1) → 2
    • returns 2 * foo(2 - 1) → 4
  • returns 2 * foo(3 - 1) → 8