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

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))

I want to count the existing routes of the given maze. (anyway, the problem itself is not that important) Problem is, I tried to count the number of cases that fit the conditions within the recursive functions.

These are two conditions that have to be counted.

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

I tried counting the conditions like this

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

But since I'm using recursive functions, if I declare count = 0 in the function, the count value stays 0.

Shortly, I just want to keep the counter unaffected by the recursive function.

Why not declare it outside the function as a global variable? You could also create a variable `calcPath.counter` and initialize it outside the function. — Arnav Borborah, Nov 12 '20 at 12:27
Does this answer your question? [Debugging recursive function to se how many times it repeats a certain calculation](https://stackoverflow.com/questions/58267788/debugging-recursive-function-to-se-how-many-times-it-repeats-a-certain-calculati) — MisterMiyagi, Nov 12 '20 at 12:28
@mkrieger1 oops, sorry. this is my first time using stack gotta change it. — user14625681, Nov 12 '20 at 12:32
you could write something like `count += calcPath(...)` instead of discarding the returned count — Ronald, Nov 12 '20 at 12:33
@ArnavBorborah I tired using a global variable, but in that case output of the 1st run affects 2nd one. I'll try the second method! thanks! — user14625681, Nov 12 '20 at 12:34

Arnav Borborah · Accepted Answer · 2020-11-12T16:21:20.940

One of the ways to solve this is by adding the count you get from each recursive function's return. When you call the recursive function, take the count that is returned and add it to the count variable in the current scope. For example:

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

An alternative solution would be to create a global variable and reset it to 0 every time the function is called (although I don't recommend this since it requires ceremony everytime the function is called).

That might look something like this:

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))

wow, I tried using global variation but why on earth did I not reset the count? haha. it's so dumb of me. Thanks for help! stack is full of kindness. impressed. — user14625681, Nov 12 '20 at 12:44
@user14625681 note that the first approach with `count += calcPath` is the best and is applicable in many cases when dealing with recursive functions. At least it doesn't require you to remember about resetting global variable. — sanyassh, Nov 12 '20 at 13:56

score 0 · Answer 2 · answered Nov 12 '20 at 14:00

I think you can use the concept of nested scope or put it simply function inside another function. For example:

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?

2 Answers2