Ответы пользователя по тегу Рекурсия
  • Как работает функция (рекурсия)?

    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 комментарий