@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
  • Вопрос задан
  • 107 просмотров
Решения вопроса 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
В поиске работы младшего python разработчика.
www.pythontutor.com/visualize.html#mode=edit

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

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

Войти через TM ID
Похожие вопросы
от 140 000 до 180 000 руб.
YLab Тольятти
от 90 000 до 150 000 руб.
Битворкс Томск
от 120 000 руб.