因此，我有一個任務，要求我使用遞歸解決迷宮問題。我將發佈作業指南，以便您可以看到我在說什麼。教授沒有多少解釋遞歸，他給了我遞歸的例子，我會發布，但我希望有人能夠給我一個更深入的遞歸解釋，以及我將如何應用它來解決一個迷宮。我沒有要求任何人寫代碼，我只是希望有一些解釋能讓我走上正確的道路。感謝任何回答的人。在Python中使用遞歸解決迷宮問題
這裏有例子，我有：
def foo():
print("Before")
bar()
print("After")
def bar():
print("During")
def factorial(n):
"""n!"""
product = 1
for i in range(n,0,-1):
product *= i
return product
def recFac(n):
"""n! = n * (n-1)!"""
if(n == 1):
return 1
return n * recFac(n-1)
def hello():
"""Stack overflow!"""
hello()
def fib(n):
"""f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1"""
if n == 0 or n == 1: #base case
return n
return fib(n-1) + fib(n-2) #recursive case
def mult(a,b):
"""a*b = a + a + a + a ..."""
#base case
if (b == 1):
return a
#recursive case
prod = mult(a,b-1)
prod *= a
return prod
def exp(a,b):
"""a ** b = a* a * a * a * a *.... 'b times'"""
#base case
if (b==0):
return 1
if (b == 1):
return a
#recursive case
return exp(a,b-1)*a
def pallindrome(word):
"""Returns True if word is a pallindrome, False otherwise"""
#base case
if word == "" or len(word)==1:
return True
#recursive case
if word[0] == word[len(word)-1]:
word = word[1:len(word)-1]
return pallindrome(word)
else:
return False
下面是指南：
您將創建能夠解決所有迷宮的迷宮履帶你給它的權力遞歸！
問題1 - 載入迷宮
之前就可以解決一個迷宮，你將不得不加載它。對於這項任務，您將使用迷宮的簡單文本格式。你可以使用這個樣本迷宮或創建你自己的。
您對這個問題的目標是加載任何給定的迷宮文件，並將其讀入到二維列表中。 例如：loadMaze（「somemaze.maze」）應該加載somemaze.maze文件並創建如下所示的列表...
[['#','#','#','#','#','#','#','#','#'],
['#','S','#',' ',' ',' ','#','E','#'],
['#',' ','#',' ','#',' ',' ',' ','#'],
['#',' ',' ',' ','#',' ','#',' ','#'],
['#', #','#','#','#','#','#','#','#']]
注意，名單已剝奪了所有的「\ r」和' \ n'字符。爲了使下一個問題更簡單，你可以將這個列表變成一個全局變量。
下一頁寫，打印出來的迷宮更加美好格式的功能：
例如，
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
與測試，然後再繼續不同的迷宮，你的代碼。
問題2 - 準備解決迷宮
之前就可以解決，你需要找到起點迷宮！在您的代碼中添加一個名爲findStart（）的函數，它將搜索迷宮（逐個字符）並返回'S'字符的x和y座標。你可能會認爲在迷宮中至多存在一個這樣的人物。如果在迷宮返回-1中找不到'S'作爲x和y座標。
在繼續之前，在多個位置（包括無位置）用'S'測試您的代碼。
問題3 - 解決迷宮！
最後，您已準備好遞歸解決迷宮！您的解決方案應該只需要一個方法：solve（y，x）
solve方法的單個實例應該解決迷宮中的單個位置。參數y和x是當前要解決的座標。你的解決方法應該完成一些事情。它應該檢查它是否正在解決'E'的位置。在這種情況下，您的解決方法已成功完成。否則，它應該嘗試遞歸地解決右邊的空間。請注意，您的方法應該只嘗試解決空格，而不是牆（'＃'）。如果該遞歸不會導致結束，那麼嘗試下來，然後離開，然後向上。如果所有失敗，你的代碼應該回溯一步，並嘗試另一個方向。
最後，在解決迷宮問題時，你的代碼應該留下它的進度指標。如果它正在搜索右側，則當前位置應該有一個'>'來代替空白空間。如果向下搜索放置'v'。如果搜索左側'<'，並且搜索'^'。如果您的代碼必須回溯移除方向箭頭，並將位置設回「」。
一旦你的迷宮解決了，再打印出迷宮。你應該看一步一步地走迷宮。 例如，
main("somemaze.maze")
#########
#S# #E#
# # # #
# # # #
#########
S爲（1,1）
#########
#S#>>v#E#
#v#^#>>^#
#>>^# # #
#########
測試代碼用不同的不同的開始位置和結束位置，並且任選地在各種迷宮。
這是我到目前爲止的代碼： 但是，代碼實際上並不是在迷宮中打印曲目，我不知道爲什麼。
def loadMaze():
readIt = open('Maze.txt', 'r')
readLines = readIt.readlines()
global mazeList
mazeList = [list(i.strip()) for i in readLines]
def showMaze():
for i in mazeList:
mazeprint = ''
for j in i:
mazeprint = mazeprint + j
print(mazeprint)
print('\n')
def solve(x,y, mazeList):
mazeList[x][y] = "o"
#Base case
if y > len(mazeList) or x > len(mazeList[y]):
return False
if mazeList[y][x] == "E":
return True
if mazeList[y][x] != " ":
return False
#marking
if solve(x+1,y) == True: #right
mazeList[x][y]= '>'
elif solve(x,y+1) == True: #down
mazeList[x][y]= 'v'
elif solve(x-1,y) == True: #left
mazeList[x][y]= '<'
elif solve(x,y-1) == True: #up
mazeList[x][y]= '^'
else:
mazeList[x][y]= ' '
return (mazeList[x][y]!= ' ')
可能會有所幫助：http://stackoverflow.com/questions/22700130/maze-solving-with-python – sshashank124
謝謝！我一直在尋找例子，但是我沒有找到對我真正有用的東西！這一個似乎非常有幫助。 – MarissaLeigh
沒問題。如果您遇到任何其他問題，只需使用新查詢更新問題 – sshashank124