How does a function (recursion) work?

Question

Python

Permutations of zeros and ones

def gen_bin(m, prefix=""):
    if m == 0:
        print(prefix)
        return
    gen_bin(m-1, prefix + "0")
    gen_bin(m-1, prefix + "1")

gen_bin(3)

Please explain how the code is executed.
gen_bin(m-1, prefix + "0") will be called three times, after which it will print the string 000. Then, as I understand it, the value 3 and an empty string are again passed to the function. What happens next? Why then gen_bin(m-1, prefix + "0") is executed 2 times and gen_bin(m-1, prefix + "1") 1 time and prints 001

Answer 1

Try drawing a call stack on a sheet:

gen_bin(3, "")                 # начальный вызов
--gen_bin(2, "" + "0")             # вызов gen_bin(m-1, prefix + "0"), где m = 3
----gen_bin(1, "0" + "0")            # вызов gen_bin(m-1, prefix + "0"), где m = 2
------gen_bin(0, "00" + "0")           # вызов gen_bin(m-1, prefix + "0"), где m = 1
--------print("000")                           # попали в условие m == 0
------gen_bin(0, "00" + "1")           # вызов gen_bin(m-1, prefix + "1"), где m = 1
--------print("001")                           # попали в условие m == 0
----gen_bin(1, "0" + "1")            # вызов gen_bin(m-1, prefix + "1"), где m = 2
------gen_bin(0, "01" + "0")           # вызов gen_bin(m-1, prefix + "0"), где m = 1
--------print("010")                           # попали в условие m == 0
------gen_bin(0, "01" + "1")           # вызов gen_bin(m-1, prefix + "1"), где m = 1
--------print("011")                           # попали в условие m == 0
--gen_bin(2, "" + "1")             # вызов gen_bin(m-1, prefix + "1"), где m = 3
----gen_bin(1, "1" + "0")            # вызов gen_bin(m-1, prefix + "0"), где m = 2
------gen_bin(0, "10" + "0")            # вызов gen_bin(m-1, prefix + "0"), где m = 1
--------print("100")                            # попали в условие m == 0
------gen_bin(0, "10" + "1")            # вызов gen_bin(m-1, prefix + "1"), где m = 1
--------print("101")                            # попали в условие m == 0
----gen_bin(1, "1" + "1")            # вызов gen_bin(m-1, prefix + "1"), где m = 2
------gen_bin(0, "11" + "0")            # вызов gen_bin(m-1, prefix + "0"), где m = 1
--------print("110")                            # попали в условие m == 0
------gen_bin(0, "11" + "1")            # вызов gen_bin(m-1, prefix + "1"), где m = 1
--------print("111")                            # попали в условие m == 0

Another option to understand how recursion works is to display the values ​​of the variables m and prefix:

n = 3

def gen_bin(m, prefix=""):
    print("  " * (n - m) + "Begin")
    print("  " * (n - m) + "m =", m)
    print("  " * (n - m) + "prefix =", prefix)

    if m == 0:
        print("  " * (n - m) + prefix)
        print("  " * (n - m) + "End")
        return
    
    print("  " * (n - m) + "Call gen_bin(m-1, prefix + '0')")
    gen_bin(m - 1, prefix + "0")

    print("  " * (n - m) + "Call gen_bin(m-1, prefix + '1')")
    gen_bin(m - 1, prefix + "1")

    print("  " * (n - m) + "End")

gen_bin(n)

Answer 2

www.pythontutor.com/visualize.html#mode=edit Paste
the code and click the "Visualize Execution" button. In the next window, you can see the step-by-step execution of the code by pressing the "Forward" button.