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

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

解决这个问题的方法之一是添加从每个递归函数的 return 中获得的计数。当您调用递归函数时，获取 returned 的计数并将其添加到当前范围内的 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]

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

How can I count the number of cases in recursive functions?

python

recursion

counter

if-statement

counting