Why does this recursive function not print done twice?

Question

I'm still trying to understand recursion and what I expected the code to print and what actually printed is different.

so here's the code which is just based off a simple example I found on youtube,

def count(n):
    if n > 0:
        print "Count 1", ", ", n

        count(n - 1)

        print "Count 2", ", ", n
    else:
        print "Done"

count(1)

and this is what it prints,

Count 1 , 1

Done

Count 2 , 1

What I expected was

Count 1 , 1

Done

Done

My understanding (which of course is wrong) is that count(1) (for the outer count function) will be called and because 1 is greater than 0 will print 1, then count(1 - 1) (inner count function) will call count(0) (outer count function) and since 0 is not greater than 1 this will print Done. Then I thought the return from count(1 - 1) (inner count function) would also return Done and since there were no other n values entered into the inner count() that would be it. I'm not understanding how done prints once and 1 prints twice???

Answer 1

Let's go through the function by hand for an input of 1:

• count(1) called (n is 1):
  • n > 0 is true, so (if clause):
    • print Count 1 , 1 (since n is 1 here)
    • count(0) called (n is 0):
      • n > 0 is false, so (else clause):
        • print Done
    • print Count 2 , 1 (since n is 1 here)

As you can see, done is only printed once. When you're faced with this type of dilemma it's often very helpful to get out the ol' pencil and notepad and trace out exactly what's happening by hand.

You can also think about a simplified version of your function by removing those first two print statements, since they shouldn't effect how many times "Done" is printed:

def count(n):
    if n > 0:
        count(n - 1)
    else:
        print "Done"

Now it should be much clearer that "Done" will only be printed once:

• count(1) called (n is 1):
  • n > 0 is true, so (if clause):
    • count(0) called (n is 0):
      • n > 0 is false, so (else clause):
        • print Done

Answer 2

Let's do a simple expansion of the count function to see what's really going on:

def count0:
    print "Done"

def count1:
    print "Count 1, 1"
    count0()
    print "Count 2, 1"

As you can see, count1 (and really any count(n) for n > 0) will never print "Done". So it is only ever printed once.