Алгоритм счетчика узлов дерева: пожалуйста, объясните эту рекурсию шаг за шагом

Question

Учитывая следующее дерево:

#                     'Mobs'
#             /          |           \
#     'NPC'          'Enemies'         'Heroes'
#     /           /       |      \            \
# 'Andrew'    'Slime'  'Goblin'  'Dragon'      'Human'
#                                     \
#                                     'Wyrm'

tree = ('Mobs', [('NPC', [('Andew', [])]), ('Enemies', [('Slime', []), ('Goblin', []), ('Dragon', [('Wyrm', [])])]), ('Heroes', [('Human', [])])])

Каждый узел представляет собой кортеж, состоящий из строки в [0] и списка возможных дочерних элементов в [1]. Следующая функция успешно возвращает счет:

def how_many(node):
    count = 1                                   
    for i in node[1]:                           
        count = count + how_many(i)             
    return count

Я пытаюсь понять, что именно он делает. Кто-то объяснил мне, что мне нужно представить себе «стеки», чтобы понять, как работает рекурсия. Позвольте мне попытаться сформулировать то, что я понял: поскольку программа не имеет всей информации на момент первого вызова, она достаточно мощна, чтобы поставить все операции на удержание, сложить их так, чтобы они были в порядке выполняется, сохраняется, продолжается до тех пор, пока не достигнет базового случая - который находится в нашей функции, когда у узла дерева нет дочерних элементов - и выдает правильное накопленное значение в нашей переменной count, чтобы он мог вернуть его, когда l oop завершено.

Я прав? Мне нужно, чтобы кто-то объяснил словами, что функция делает шаг за шагом, если это возможно.

Answer 1

В основном вы можете думать о коробках. Допустим, мы хотим считать коробки.

1. У вас большая коробка мобов. У вас есть одна коробка count = 1 Начало вашей рекурсии.

2. Вы открываете коробку. Вы видите три маленьких коробочки (NP C, враги, герои). for i in node[1]

3. Вы берете первую коробку (NP C) и спрашиваете, сколько у меня коробок в NP C. count = count + how_many(i).

4. У вас есть 1 ящик (NP C) count = 1

5. Вы открываете ящик и видите меньший ящик (Андрей) for i in node[1].

6. Вы снова берете коробку и спрашиваете, сколько у меня коробок в Эндрю. count = count + how_many(i)

7. У вас есть 1 коробка (Андрей). count = 1

8. Вы открываете коробку и не видите меньшую коробку. Вы не вводите для l oop for i in node[1]

9. Вы возвращаете счет, который равен 1.

10 Вы возвращаетесь к Коробка до (NP C) вы получаете 1 обратно от how_many(i) (от Эндрю) и получаете 1 форму NP C. 1 + 1 = 2

11 В NP C нет других полей, поэтому вы выходите из функции для l oop и возвращаете счетчик, равный 2.

Вы вернулись в свой первый ящик (моб). Вы получаете 2 обратно и получаете 1 из коробки моба. 1 + 2 = 3.

Вы все еще находитесь в поле для l oop и отметьте следующую ячейку (враги).

Вы делаете то же самое вкратце: враги вернут 5 (враги, слизь, гоблин, дракон, змей). Вы считаете 3 + 5 = 8.

Последняя коробка все еще там (герои)

Сделайте то же самое вкратце: герои вернут 2 (герои, люди) и вы количество 8 + 2 = 10.

Последнее возвращение count = 10

результат = 10

Answer 2

Вот более простой вариант использования для рекурсии: факториальная функция n! = n * (n-1) *... * 2 * 1

def factorial(n):
    if n == 0:
        result = 1
    else: result = n * factorial(n-1)
    return result

print(factorial(2))

Что здесь происходит?

• factorial(2) вызывается. Он переходит в состояние else и ждет factorial(1) результата
• factorial(1). Он переходит в состояние else и затем ждет factorial(0) результата
• factorial(0). На этот раз он находится в состоянии if. Результат 1 возвращается.
• we go возвращается в функцию factorial(1), где мы можем решить строку result = n * factorial(n-1). Возвращается результат 1 * 1 = 1.
• мы наконец go вернулись в функцию factorial(2), где мы можем решить строку result = n * factorial(n-1). Возвращается результат 1 * 1 * 2 = 2.
• он печатает 2