Понимание потока в рекурсии

Начните с меньшего числа, чтобы вы могли сопоставить все рекурсии сразу. Я также собираюсь немного переписать вашу функцию для простоты воспроизводимости.

def divide_by_2(num):
    if num == 0:
        return  # we're done
    divide_by_2(num//2)
    print(num)

Теперь делим на 5 ...

divide_by_2(5)
-> divide_by_2(2); print(5)
-> divide_by_2(1); print(2); print(5)
-> divide_by_2(0); print(1); print(2); print(5)
-> return; print(1); print(2); print(5)

В основном: поскольку вы поместили рекурсивный вызов перед остальной функцией, она должна завершить свою рекурсию, прежде чем она сможет продолжить.

Возьмите палец и следуйте строкам кода (начиная с нижней строки, поскольку это то, что запускает все), каждый раз, когда вы сталкиваетесь с div_by_2, возвращайтесь к началу

Вы заметите, что вы начинаете входить в функцию с 39 и нажимаете еще один вызов div_by_2, прежде чем что-либо печатать.

Вы будете продолжать в том же духе, пока не дойдете до 1, после чего вы пропустите вызов div_by_2, а затем начнете печатать вещи в обратном порядке по мере раскручивания стека вызовов.

Все разворачивается, потому что, когда вы выходите из вызова функции, код продолжается со следующей строки после вызова функции.

Следующая строка - это оператор печати, поэтому первое, что нужно напечатать, - результат наименьшего деления.

Возможно, вам будет очень полезно использовать язык с интерактивным отладчиком, чтобы вы могли пошагово выполнить код и увидеть, как он работает, но если у вас этого нет, подумайте об этом как о нескольких уровнях отступов кода:

divide_by_2(64)

print(64)



divide_by_2(64)
  divide_by_2(32)

  print(32)
print(64)

Каждый раз, когда вы выполняете рекурсию, вы копируете и вставляете пару разделить / печать в среднюю пустую строку, и отступ увеличивается, чтобы продемонстрировать, что стек вызовов становится длиннее.

divide_by_2(64)
  divide_by_2(32)
    divide_by_2(16)

    print(16)
  print(32)
print(64)


divide_by_2(64)
  divide_by_2(32)
    divide_by_2(16)
      divide_by_2(8)
        divide_by_2(4)
          divide_by_2(2)
            divide_by_2(1)
            print(1)
          print(2)
        print(4)
      print(8)
    print(16)
  print(32)
print(64)

Вы спросили, какая печать печатается первой, и что будет проще, если вы говорите о том факте, что ваш код содержит два оператора печати - тот, который встречается первым в исходном коде.

Если вы имеете в виду, почему 39 печатается в последний раз, то это потому, что ваш код использует все ресурсы настолько глубоко, насколько может, прежде чем он перестанет повторяться, и печать выполняется на выходе. Если вы печатали до того, как рекурсивно переходили к функции деления, то числа начинались бы с 39 и становились меньше.

Так как 39 больше 1, он входит в начальный оператор if. Первая строка кода в этом блоке указывает ему рекурсивно вызывать себя с помощью divide_by_2(num // 2) (принимая целое число Floor). Нет никакого попадания в оператор печати - он просто помещает другой divide_by_2 в стек вызовов, divide_by_2(19). Таким образом, он будет продолжать добавлять в стек вызовов и вызывать операторы печати нет, пока num не станет <1.

На вершине стека вызовов вы получаете 1 1, потому что этот вызов нет входит в условное выражение if, он немедленно направляется в print(num % 2,num).

После этого он возвращается в стек вызовов, где каждая функция может выполнять (и завершать) как print(num), так и print(num % 2, num), пока в стеке больше не останется функций для выполнения.

Надеюсь, что это немного объяснило «теорию», лежащую в основе этого.

Если мы возьмем ваш код (и добавим номера строк для ясности)

1 def divide_by_2(num):
2    if num > 1:
3       divide_by_2(num // 2)
4       print(num)
5    print(num % 2,num)

Затем пропустите меньшее число строка за строкой в ​​качестве примера.

divide_by_2(4)

(call 1, num==4) Line 2 is executed, it is greater than 1 so move to line 3

(call 1, num==4) Line 3 calls the same function. It will not continue to line 4 until the function call 2 is finished executing and returns. We have not yet called a print statement so nothing shows!

(call 2, num==2) Line 2 is executed, it is greater than 1 so move to line 3

(call 2, num==2) Line 3 Recurse through the same function again will not continue executing until call 3 is finished. Still no print statement

(call 3, num==1) Line 2 is executed, it is equal to 1, move to line 5

(call 3, num==1) Line 5 We finally have a print statement! We are at the innermost call with num==1 so "1 1" is printed. Now that this function has finished, we return to line 4 in the most recent call which in this case is call 2

(call 2, num==2) Line 4 With the function returning, we start executing the next line which is print(num) which simply print "2"

(call 2, num==2) Line 5 We have another print statement, this one prints "0 2". Now that call 2 is finished executing, call 1 resumes

(call 1, num==4) Line 4 prints "4"

(call 1, num==4) Line 5 prints "0 4"

Execution ends

This gives the end result of:

1 1

2

0 2

4

0 4

Ключевым моментом, который следует помнить о том, почему числа печатаются от наименьшего к наибольшему, является то, что поток в этой программе печатает операторы после, рекурсивно переходящие в следующую функцию. Это приводит к поведению call 1 -> call 2 -> call 3 -> print from call 3 -> print from call 2 -> print from call 1.

Самый простой способ разобраться в рекурсии - это просмотреть код построчно на бумаге или в уме. Надеюсь, эта разбивка поможет.