Python 再帰関数 returnの性質

実現したいこと

PythonにてDFS（再帰）を用いて、特定の条件を満たすルートを全て洗い出したいです。

前提

Atcoder で以下の問題をDFS（再帰）を用いて解きたいと考えています。
https://atcoder.jp/contests/abc293/tasks/abc293_c

発生している問題・エラーメッセージ

下に自分の書いたコードを添付します。
17行目で”ゴールに辿り着いた際、一段階戻って他の経路の探索を続ける”ことができないです。
ですが、returnを取り外すと継続できます。
また13行目で行っている、”条件に合わなかった場合、一段階戻って他の経路の探索を続ける”についてはreturnがついていても可能です。
これはなぜなのでしょうか。
returnにはどのようなルールがあるのか理解できずにいます。

該当のソースコード

python
1import sys
2 
3sys.setrecursionlimit(10**7)
4
5H, W = map(int, input().split())
6
7masu = [tuple(map(int, input().split())) for _ in range(H)]
8
9check = set()
10cnt = 0
11
12def dfs(x,y):
13    if masu[y][x] in check:
14        #print(check)
15        return
16    check.add(masu[y][x])
17    if x == W-1 and y == H-1:
18        #print("flag")
19        global cnt 
20        cnt += 1
21        return
22    
23    if x < W-1:
24        dfs(x+1, y)
25    if y < H-1:
26        dfs(x, y+1)
27    
28    check.remove(masu[y][x])
29
30dfs(0,0)
31

試したこと

再帰の深さの遍歴を確認しました。
returnをつけてもゴールには規定回数（３回）たどり着けているようですが、カウントが１回だけになっているようで、ここに原因があるようですが理由まではわかりませんでした。。。

python
1import sys
2 
3sys.setrecursionlimit(10**7)
4
5H, W = map(int, input().split())
6
7masu = [tuple(map(int, input().split())) for _ in range(H)]
8
9check = set()
10cnt = 0
11depth = 0
12def dfs(x,y, depth):
13    depth += 1
14    print(depth)
15    global cnt 
16    if masu[y][x] in check:
17        #print(check)
18        cnt += 0
19        return
20    check.add(masu[y][x])
21    
22    if x == W-1 and y == H-1:
23        #print("flag")
24        cnt += 1
25        return
26    
27    if x < W-1:
28        dfs(x+1, y, depth)
29    if y < H-1:
30        dfs(x, y+1, depth)
31    
32    check.remove(masu[y][x])
33
34dfs(0,0,0)
35    
36#print(cnt)
37