Попробуйте нарисовать на листе стек вызовов:
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
Еще как вариант, чтобы понять как работает рекурсия, выводить значения переменных m и 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)
