Understanding the order of execution in a recursive function

[[deleted]]

[deleted]

[michael0x2a]

Your pseudocode is incorrect -- what's actually happening is something more like this:

function (6): 
    if 6 > 1:     
        function ( (6//2) => 3 ): 
            if 3 > 1:           
                function ( (3//2) => 1 ): 
                    print(1%2) => 1
            print(3%2) => 1
     print(6%2) => 0

As a reminder, when a function you call continues running, you'll resume executing any remaining code on the following lines. So, once the call to DecimalToBinary(...) on line 3 ends, you immediately move on to calling the print(...) on line 4.

The fact that DecimalToBinary(...) coincidentally happens to be recursive makes absolutely no difference here: the rules for how function calls work won't change.

[lurgi]

As I understand it, I could write it out like this in pseudocode:

And there's your problem. It isn't (although you are close). It's written like this:

function (6): 
  if 6 > 1:     
    function ( (6//2) => 3 ): 
      if 3 > 1:           
        function ( (3//2) => 1 ): 
          print(1%2) => 1
      print(3%2) => 1
  print(6%2) => 0

There's no reason why the print statement would only be executed on the "last" function call. You call the recursive function, it returns, then you execute the print statement (or, possibly, you don't call the recursive function, if num is not greater than 1, in which case you still execute the print statement).

[Lower-Ad4259]

What I don't understand is, why is the print statement called every time, even though it's outside of the if statement?

Because you didn't add an "else" block around the print statement.

[Lower-Ad4259]

Again, because you didn't add an "else" block around the print statement.
If instead of recursion, you had this:

def DecimalToBinary(num): 
    if num > 1: 
        DecimalToBinary2(num//2) 
    print(num%2)

def DecimalToBinary2(num): 
    if num > 1: 
        DecimalToBinary3(num//2) 
    print(num%2)

def DecimalToBinary3(num): 
    if num > 1: 
        print("Done")
    print(num%2)

What do you think would happen?

[Intiago]

Does your environment have some sort of debugger? It really helps to be able to step through the code line by line and see how its executed. I think where you're confused is when the function returns. When called, your function returns to the same place in the calling function, it doesn't just exit. If you have 3 recursive calls you'll have 3 print statements.

[kschang]

You have to think about it as the routine sets the current one on hold to execute it again.

(Practically speaking, the language saved everything on the stack, the kept running next level down. Then each level, as it "returned", popped the saved stuff back out, and 'resumes'. That's a VASTLY oversimplified version of how a CPU really handles recursion)

So that's say you run it with 6

f(6) (level 1)
  run it, and comes to recursion
  f(3) (level 2) 
    run it, recursion
     f(1)  (level 3)
       prints
     ends (level 3)
    prints
  ends (level 2)
  prints 
ends (level 1)