所以，我有一个作业，要求我使用递归来解决迷宫。我将发布作业准则，以便您了解我在说什么。教授没有对递归进行太多解释，他给了我们递归的例子，我会在上面发表，但是我希望有人可以对递归进行更深入的解释，以及如何将其应用于求解。迷宫。我并不是要任何人来编写代码，我只是希望一些解释可以使我走上正确的道路。谢谢任何回答的人。
以下是我的示例：
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坐标。您可以假设迷宫中最多存在一个这样的角色。如果在迷宫中未找到“ S”，则返回-1作为x和y坐标。
继续之前，请在多个位置（包括无位置）使用'S'测试您的代码。
问题3-解决迷宫！
最后，您已准备好递归解决迷宫！您的解决方案应该只需要一个方法：resolve（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]!= ' ')
这是我对CodeEval的The Labirynth挑战的解决方案：
import sys
sys.setrecursionlimit(5000)
class Maze(object):
FLOOR = ' '
WALLS = '*'
PATH = '+'
def __init__(self):
self.cols = 0
self.rows = 0
self.maze = []
def walk_forward(self, current_k, r, c):
self.maze[r][c] = current_k
next_k = current_k + 1
# up
if r > 1:
up = self.maze[r - 1][c]
if up != self.WALLS:
if up == self.FLOOR or int(up) > current_k:
self.walk_forward(next_k, r - 1, c)
# down
if r < self.rows - 1:
down = self.maze[r + 1][c]
if down != self.WALLS:
if down == self.FLOOR or int(down) > current_k:
self.walk_forward(next_k, r + 1, c)
# left
if c > 1:
left = self.maze[r][c - 1]
if left != self.WALLS:
if left == self.FLOOR or int(left) > current_k:
self.walk_forward(next_k, r, c - 1)
# right
if c < self.cols - 1:
right = self.maze[r][c + 1]
if right != self.WALLS:
if right == self.FLOOR or int(right) > current_k:
self.walk_forward(next_k, r, c + 1)
def walk_backward(self, r, c):
current_k = self.maze[r][c]
if not isinstance(current_k, int):
return False
self.maze[r][c] = self.PATH
up = self.maze[r - 1][c] if r > 0 else None
down = self.maze[r + 1][c] if r < self.rows - 1 else None
left = self.maze[r][c - 1] if c > 1 else None
right = self.maze[r][c + 1] if c < self.cols else None
passed = False
if up and isinstance(up, int) and up == current_k - 1:
self.walk_backward(r - 1, c)
passed = True
if down and isinstance(down, int) and down == current_k - 1:
self.walk_backward(r + 1, c)
passed = True
if left and isinstance(left, int) and left == current_k - 1:
self.walk_backward(r, c - 1)
passed = True
if right and isinstance(right, int) and right == current_k - 1:
self.walk_backward(r, c + 1)
def cleanup(self, cleanup_path=False):
for r in range(0, self.rows):
for c in range(0, self.cols):
if isinstance(self.maze[r][c], int):
self.maze[r][c] = self.FLOOR
if cleanup_path and self.maze[r][c] == self.PATH:
self.maze[r][c] = self.FLOOR
def solve(self, start='up', show_path=True):
# finding start and finish points
upper = lower = None
for c in range(0, self.cols):
if self.maze[0][c] == self.FLOOR:
upper = (0, c)
break
for c in range(0, self.cols):
if self.maze[self.rows - 1][c] == self.FLOOR:
lower = (self.rows - 1, c)
break
if start == 'up':
start = upper
finish = lower
else:
start = lower
finish = upper
self.cleanup(cleanup_path=True)
self.walk_forward(1, start[0], start[1])
length = self.maze[finish[0]][finish[1]]
if not isinstance(length, int):
length = 0
if show_path:
self.walk_backward(finish[0], finish[1])
self.cleanup(cleanup_path=False)
else:
self.cleanup(cleanup_path=True)
return length
def save_to_file(self, filename):
with open(filename, 'w') as f:
f.writelines(str(self))
def load_from_file(self, filename):
self.maze = []
with open(filename, 'r') as f:
lines = f.readlines()
for line in lines:
row = []
for c in line.strip():
row.append(c)
self.maze.append(row)
self.rows = len(self.maze)
self.cols = len(self.maze[0]) if self.rows > 0 else 0
def get_maze(self):
return copy.copy(self.maze)
def __str__(self):
as_string = u''
for row in self.maze:
as_string += u''.join([str(s)[-1] for s in row]) + "\n"
return as_string
maze = Maze()
maze.load_from_file(sys.argv[1])
maze.solve(show_path=True)
print str(maze)
（约会我，我实际上在高中时在COBOL中遇到了这个问题。）
您可以考虑解决迷宫的步骤。
当您采取步骤时，每次都适用相同的规则。由于每次都应用相同的规则，因此您可以为每个步骤使用完全相同的一组指令。当您执行一个步骤时，只需再次调用同一例程，即可更改参数以指示新步骤。那是递归。您可以一次解决一个问题，以解决问题。
注：某些递归解决方案将问题分解成两半，使每一半独立于另一半解决，这在两个解决方案实际上是独立的时才有效。它在这里不起作用，因为每个步骤（解决方案）都取决于先前的步骤。
如果碰到死角，您将退出死角，直到找到仍然可以检查正方形的步骤。
有用的提示：您没有在出口[返回途中。您可以执行此操作，因为每一步都会在执行下一步之前记住它所在的正方形。相反，您在尝试过的每个方格中都打了一个标记，只说：我去过这里，无需再次检查。在打印解决方案之前，请清理它们。