@5HT2A

Как работает функция (рекурсия)?

Перестановки нулей и единиц
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)

Объясните пожалуйста как происходит выполнение кода.
gen_bin(m-1, prefix + "0") будет вызвана три раза, после напечатает строку 000. Затем я так понимаю в функцию снова передается значение 3 и пустая строка. Что происходит дальше? Почему затем gen_bin(m-1, prefix + "0") выполняется 2 раза и gen_bin(m-1, prefix + "1") 1 раз и печатает 001
  • Вопрос задан
  • 444 просмотра
Решения вопроса 1
2lazy4dat
@2lazy4dat
Попробуйте нарисовать на листе стек вызовов:
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)
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
igorzakhar
@igorzakhar
www.pythontutor.com/visualize.html#mode=edit

Вставляй код и нажимай кнопку "Visualize Execution". В следующем окне можешь посмотреть пошаговое выполнение кода нажимая кнопку "Forward".
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы