如何计算递归函数中的事例数？

Question

def calcPath(trace_map, x, y):
    n = len(trace_map)
    count = 0
    if x > n - 1 or y > n - 1:
        pass
    elif x < n and y < n:
        if x + trace_map[x][y] == (n - 1) and y == (n - 1):
            count += 1
        elif x == (n - 1) and y + trace_map[x][y] == (n - 1):
            count += 1
        else:
            calcPath(trace_map, x + trace_map[x][y], y)
            calcPath(trace_map, x, y + trace_map[x][y])
    return count


if __name__ == "__main__":
    trace_map = [
        [1, 2, 9, 4, 9],
        [9, 9, 9, 9, 9],
        [9, 3, 9, 9, 2],
        [9, 9, 9, 9, 9],
        [9, 9, 9, 1, 0],
    ]
    print(calcPath(trace_map, 0, 0))

    trace_map = [[1, 1, 1], [1, 1, 2], [1, 2, 0]]
    print(calcPath(trace_map, 0, 0))

我想计算给定迷宫的现有路线。（无论如何，问题本身并不那么重要） 问题是，我试图计算符合递归函数条件的情况的数量

这是必须计算的两个条件

if x + trace_map[x][y] == (n - 1) and y == (n - 1):
if x == (n - 1) and y + trace_map[x][y] == (n - 1):

我试着像这样计算条件

count = 0 
if condition = True: 
count +=1

但由于我使用的是递归函数，如果我在函数中声明count=0，则计数值保持为0

简而言之，我只想让计数器不受递归函数的影响

Answer 1

解决此问题的方法之一是将从每个递归函数返回的计数相加。调用递归函数时，获取返回的计数并将其添加到当前范围中的count变量中。例如：

def calcPath(trace_map, x, y):
    n = len(trace_map)
    count = 0
    if x > n - 1 or y > n - 1:
        pass
    elif x < n and y < n:
        if x + trace_map[x][y] == (n - 1) and y == (n - 1):
            count += 1
        elif x == (n - 1) and y + trace_map[x][y] == (n - 1):
            count += 1
        else:
            count += calcPath(trace_map, x + trace_map[x][y], y)
            count += calcPath(trace_map, x, y + trace_map[x][y])
    return count

另一种解决方案是创建一个全局变量，并在每次调用函数时将其重置为0（尽管我不建议这样做，因为每次调用函数时它都需要设置）

可能看起来像这样：

count = 0 # Global variable

def calcPath(trace_map, x, y):
    global count
    n = len(trace_map)
    if x > n - 1 or y > n - 1:
        pass
    elif x < n and y < n:
        if x + trace_map[x][y] == (n - 1) and y == (n - 1):
            count += 1
        elif x == (n - 1) and y + trace_map[x][y] == (n - 1):
            count += 1
        else:
            calcPath(trace_map, x + trace_map[x][y], y)
            calcPath(trace_map, x, y + trace_map[x][y])


if __name__ == "__main__":
    trace_map = [
        [1, 2, 9, 4, 9],
        [9, 9, 9, 9, 9],
        [9, 3, 9, 9, 2],
        [9, 9, 9, 9, 9],
        [9, 9, 9, 1, 0],
    ]
    print(calcPath(trace_map, 0, 0))

    # Use count in some way

    count = 0 # Reset the count

    trace_map = [[1, 1, 1], [1, 1, 2], [1, 2, 0]]
    print(calcPath(trace_map, 0, 0))

Answer 2

我认为您可以使用nested scope的概念，或者将它简单地放在另一个函数中。例如：

def fuc(args):
    if not args:
        return 0
    else:
        fuc.count += 1
        return args[0] + fuc(args[1:])

def fac(fuc, args):
    fuc.count = 0
    return fuc(args), fuc.count

print(fac(fuc, [1, 2, 3]))
print(fac(fuc, [4, 5, 6, 7]))

(6, 3)
(22, 4)
[Finished in 0.1s]