Order of execution of lines in a recursive function

Question

Let's say I have a piece of code to convert decimal numbers to binary in Python.

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

What I don't understand is, why is the print statement called every time, even though it's outside of the if statement? Why does it work by printing the remainders of each num%2 in reverse?

If the function is called (in the if statement) recursively, shouldn't the print statement only print when num <= 1, so only print one last number? Can someone explain this to me, please? Or tell me the order in which the lines in this function are executed?

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

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

Answer 1

A recursion with a print() isn't like a return, which would end the function immediately on hitting the return. The recursions all happen, then the prints all happen in order from the deepest to the shallowest recursion. One way to help understand is to add a recursion number argument into the function definition, then increment it with each recursion and print it to see what order the numbers are being printed.

def DecimalToBinary(num, recursion_num):
    recursion_num +=1
    if num > 1:
        print(f'"stacking" {recursion_num} function calls')
        DecimalToBinary(num//2,recursion_num)
    print(f'"unstacking" and printing recursion number {recursion_num}')
    print(num%2)

Then call it with the number to see it fold and unfold

DecimalToBinary(10,0)

"stacking" 1 function calls
"stacking" 2 function calls
"stacking" 3 function calls
"unstacking" and printing recursion number 4
1
"unstacking" and printing recursion number 3
0
"unstacking" and printing recursion number 2
1
"unstacking" and printing recursion number 1
0

Answer 2

Let me tell you a little story about Alice and her friends

Alice was trying to convert the number six into binary. She noticed that it was greater than one! Alice new that numbers greater than one were not to be trifled with, so she called in her friend Bob to help.

First, Alice divided six by two and got the number three.

"Hey Bob, would you please write the binary representation of three on the blackboard for me?" she asked.

Bob was not one to abandon his friend in time of need, so he agreed. While he was working, Alice took a well deserved pause at the coffee machine. When she came back, Bob was finished. Alice calculated the remainder of six modulo two and got the number 0, so she wrote 0 on the blackboard right next to the numbers already written by Bob.

But how did Bob do it?

While trying to convert the number three in binary, Bob noticed that it was greater than one! Bob didn't want to make a mistake and disappoint Alice, so he called in his friend Charlie to help.

First, Bob divided three by two and got the number one.

"Hey Charlie, would you please write the binary representation of one on the blackboard for me?" he asked.

Charlie was always ready to help Bob impress everyone, so he heartily agreed. While he was working, Bob went to the library and read a chapter of his favourite book, Gödel, Escher and Bach. When Bob came back, Charlie was finished. Bob calculated the remainder of three modulo two and got the number one, so he wrote one on the blackboard right next to the number already written by Charlie.

But how did Charlie do it?

Charlie tried very hard to convert the number one to binary and noticed that one was not greater than one. That was very good news, because Charlie had never been too confident with large numbers. He decided he could handle the task on his own, and did not call any friend for help.

Charlie calculated the remainder of one modulo two and got the number one. So he wrote one on the blackboard.

Recalling the story in order

First, Charlie wrote one on the blackboard, while Bob was reading and Alice was drinking coffee.

Then, Bob wrote one on the blackboard, while Alice was still drinking coffee.

Then, Alice wrote zero on the blackboard.

Finally, the number 110 was written on the blackboard.

Answer 3

Your interpretation is missing the fact that after each recursive call returns, control will continue with the remainder of the code in the function from after the call -- in this case the print(num%2) statement at the end.

Adding the missing parts at the end of your pseudo-code, this gives:

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

Hence, the digits 1, 1, 0 are printed -- in order from the deepest level of recursion to the shallowest (initial) call.