solve_recursive_plain

普通遞迴數路徑

從左上角走到右下角，只能往下或往右，遇到 # 不能走。這段程式用「站在每一格問兩個小問題」的方式，把路徑數一條一條加起來。

本例答案
2
3×3 格、中間有障礙

① 題目長什麼樣子

START(0,0)
(0,1)
(0,2)
(1,0)
#(1,1)
(1,2)
(2,0)
(2,1)
GOAL(2,2)
i 是第幾列（往下加 1），j 是第幾行（往右加 1）。

核心想法：把大問題丟給小問題

count(i, j)
從這格到終點有幾條路
=
count(i+1, j)
先往下走一步
+
count(i, j+1)
先往右走一步

站在任何一格，往終點的路只有兩種開頭：第一步往下或第一步往右。所以這一格的路徑數 = 下面那格的路徑數 + 右邊那格的路徑數。這就是遞迴——同一個問題，換一格再問一次。

% MOD
路徑數會大到爆掉，所以每加完一次就取餘數 10**9 + 7，讓數字維持在可控範圍。

② 程式碼的四個 if，其實就是四種「站在格子上的處境」

def count_paths(i, j):
    ① if i >= H or j >= W:
           return 0

    ② if grid[i][j] == '#':
           return 0

    ③ if i == H - 1 and j == W - 1:
           return 1

    ④ return (count_paths(i + 1, j)
            + count_paths(i, j + 1)) % MOD
✕
① 走出格子外 → 回傳 0
走過頭掉出棋盤了，這條走法根本不成立，所以貢獻 0 條路。
#
② 踩到障礙 → 回傳 0
這格是牆，站不上去，後面也不用問了，同樣是 0 條路。
1
③ 已經站在終點 → 回傳 1
從終點到終點，就是「什麼都不用走」這一種走法，算 1 條。這是遞迴的底層出口。
↓+→
④ 其他情況 → 問下面 ＋ 問右邊
自己不算，把問題丟給兩個鄰居，等它們回報數字再加起來取餘數。

③ 整棵遞迴樹攤開來看

繼續往下問 回傳 1 回傳 0
count(0,0)= 2
count(1,0)= 1
count(2,0)= 1
count(3,0) 越界 = 0
count(2,1)= 1
count(3,1) 越界 = 0
count(2,2) 終點 = 1第 1 次算
count(1,1) 障礙 = 0
count(0,1)= 1
count(1,1) 障礙 = 0重複
count(0,2)= 1
count(1,2)= 1
count(2,2) 終點 = 1又算一次
count(1,3) 越界 = 0
count(0,3) 越界 = 0
怎麼讀這棵樹
往下讀＝往深處遞迴。每縮排一層，就是「又走了一步」，還沒有任何答案產生。
答案是從葉子往上長出來的。只有綠色的終點會生出 1，其他葉子都是 0；每個父節點把兩個小孩的數字相加往上回報。
最後 2 = 1 + 1。兩片綠葉子，就是這張圖真的存在的兩條路：↓↓→→ 和 →→↓↓。
虛線框＝同一格被算了兩次
3×3 只重複兩次還看不出問題；格子一大，重複次數會呈指數成長，這就是「普通遞迴」很慢的原因。

④ 一步一步跟著跑一次（共 15 次呼叫）

按「下一步」看電腦實際走訪的順序
{{ c.label }} {{ c.note }} {{ c.badge }}
STEP {{ stepNo }} / 15
目前呼叫
{{ stepCall }}
{{ stepTag }} {{ stepNote }}
呼叫堆疊
最下面是最新的一層
{{ s.label }}
已找到的完整路徑
{{ found }}
已用掉的呼叫次數
{{ stepNo }}

⑤ 這個寫法哪裡不好

2ⁿ
呼叫次數指數成長
每一格都分裂成兩個呼叫，深度是 H+W。20×20 的格子就要跑上億次，直接超時。
↺
同一格重複算很多次
上面那棵樹裡 count(2,2) 就被算了兩次，答案卻永遠一樣——白做工。
✓
解法：把算過的記下來
加一個字典（memo）或改成表格 DP，每格只算一次，複雜度立刻降到 H×W。