Локальная переменная в рекурсивном вызове

Question

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

def count_less(self, item): 
    """(BST, object) -> int 
    Return the number of items in BST that less than item. 
    """ 
    return BST.count_less_helper(self.root, item) 

# Recursive helper function for count_less. 
def count_less_helper(root, item): 
    count = 0 
    if root: 
     if root.item < item: 
      count += 1 
      count += BST.count_less_helper(root.left, item) 
      count += BST.count_less_helper(root.right, item) 
     elif root.item > item: 
      count += BST.count_less_helper(root.left, item) 
    return count 

Answer 1

Вы устанавливаете count локально на 0 в начале функции, но затем вы добавляете все счеты от более поздних рекурсивных вызовов к нему, прежде чем вернуть его обратно вызывающему. Каждая последующая функция начинается с 0, но затем добавляет 1 + подсчет последующих вызовов.

Answer 2

почему локальная переменная count может вспомнить общее

В факт, он не «помнит».

На каждом уровне рекурсии значение count происходит с нуля, используя значения, возвращаемые рекурсивными вызовами.

Answer 3

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