Двойной рекурсивный вызов

Question

 def print_numbers(n, k):  
 """Print all numbers that (A) can be formed from the digits  of `n` in reverse
order and (B) are multiples of `k`.
  Args:  n (int): The number that results must use digits from. 
 k (int): The number that results must be multiples of.    
  >>> print_numbers(97531, 5) 
     135 
     15
     35"""
   def inner(n,s):
     if n == 0:
        if s % k == 0 and s > 0:
             print(s)
     else:
          inner(n // 10, s*10 + n % 10) #first
          inner(n // 10, s) #second
   inner(n,0)

У меня есть некоторые проблемы с пониманием части рекурсивных вызовов.Как я понимаю, второй рекурсивный вызов не может быть вызван до того, как первый достигнет фазы, когда он должен дать возвращаемое значение.Однако, что делает первый вызов (в примере): он дает внутренний (9753,1), внутренний (975,13), внутренний (97,135), внутренний (9,1357), внутренний (0,13579)

Так как тогда n равно 0, s (13579) не делится на k (5), поэтому он ничего не печатает.Более того, возвращаемое значение равно None в зависимости от конструкции функции.Итак, когда достигнута внутренняя (0,13579) фаза, второй рекурсивный вызов должен начать работать, однако он будет постоянно пытаться 0 // 10 и не будет продолжаться.

Это мое понимание.Можете ли вы указать, где я не прав?

Answer 1

Пара вопросов.Во-первых, думайте о рекурсии как о иерархии стеков.

Однако, что делает первый вызов (в примере): он дает внутренний (9753,1), внутренний (975,13), внутренний (97,135), внутренний (9,1357), inner (0,13579)

Одна из проблем здесь заключается в том, что первый вызов не блокируется только для выполнения этой одной строки.каждый вызов порождает два новых вызова в блоке else.Подробнее об этом через секунду

Итак, когда достигнута внутренняя (0,13579) фаза, второй рекурсивный вызов должен начать работать, однако он будет постоянно пытаться 0 // 10 и не будет продолжаться.

Это недостатки.Почему значение "n" должно быть нулевым для этого вызова?Если вы помните, первый экземпляр этого вызова был во время блока else, который был обработан для n = 97531.

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

Более простой способ - рассмотреть каждый стек отдельно.

stack 1: n = 97531
else: #n//10 = 9753
    child1 (9753,1)
    child2 (9753,0)
            stack2 - child1:
            else: #n//10 = 975
                child11 (975,13)
                child12 (975,1)
            stack2 - child2:
            else: #n//10 = 975
                child21 (975, 3)
                child22 (975, 0) #and so on.

Для каждого уровня иерархии определены свои переменные, и он будет порождатьсярекурсивные функции, которые принадлежат к более низкой иерархии, пока вы не дойдете до базового варианта отдельно, так сказать, для каждого «ответвления / спавна».

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