[問題]使用遞迴解迷宮卻遇到stack overflow

[ar0n77777 (property)]

各位大大好

某份作業需要解迷宮
我參考了網路上的遞迴算法
但是卻總是遇到stack overflow
想給各位抓藥一下

其中 0 是可以走的路徑
如果確定是正確路徑我就標記 1
起點為矩陣ret[1][0]
終點為ret[99][100]

https://imgur.com/LxVeeUY.jpg

terminal執行結果
https://imgur.com/inKi4aR.jpg

會stackoverflow我想是因為無法走到終止條件(?)
但是實在不知問題出在哪邊QAQ

第一次寫遞迴程式麻煩各位學長姐鞭小力一點嗚嗚
謝謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.225.142.235
※ 文章網址: https://www.ptt.cc/bbs/Python/M.1524883201.A.A7E.html
→ djshen: 你先把走的路徑印出來看跟你想的一不一樣
→ djshen: 然後先從小一點的試試看
推 a0919610611: 你i,j都沒終止條件阿walk(ret,i,j+1) j會加到無限大
推 s9041200: 沒設邊界條件。
→ s9041200: 如果設了還是爆掉，就用dp或單源最短路徑試試。
推 froce: 最後一招就是改sys.setrecursionlimit()
感謝各位 我加入了邊界條件之後還是爆掉
我加入 if i<0 or i>100 or j<0 or j>100:
           return False
目前是想到還能用DFS 但也是需要用到遞迴
※ 編輯: ar0n77777 (140.112.25.47), 04/30/2018 14:16:31
推 Yshuan: 你把size先改成30以內看是否有結果
→ Yshuan: DFS可以用迴圈寫的 和BFS差別在容器是stack而非queue
推 Yshuan: 文章中的寫法 一個點會被重複拜訪阿 2x2也會overflow
推 Yshuan: 漏看line 7, 那麼就是改小size先確定這會動 再優化吧
推 handsomeLin: 因為你遞迴寫的方式會把整個MATRIX走滿 也就是100*10
→ handsomeLin: 0 在建立boundary情形下 先往j + 1走到底 j == 100
→ handsomeLin: 時又往下 i + 1下走 總而言之八成會繞完整個matrix
→ handsomeLin: 然後你not只用在一個條件下 估計走一走都是True
→ handsomeLin: 應該八成原本標記的1都會又會變成0