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.

Species

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. – Metaphrase

Does this answer your question? Debugging recursive function to se how many times it repeats a certain calculation – Questionless

@mkrieger1 oops, sorry. this is my first time using stack 😅 gotta change it. – Species

you could write something like count += calcPath(...) instead of discarding the returned count – Hyperform

@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! – Species

@Species I added an answer that's easier to implement – Metaphrase

Answer 1

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

Metaphrase

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.🥰 – Species

@Species 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. – Huss

Answer 2

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]

Lindstrom