title: Solving a maze using recursion in python
body: <p>So, I have an assignment which asks me to solve a maze using recursion. I will post the assignment guidelines so you can see what I am talking about. The professor didn't explain recursion that much, he gave us examples of recursion, which I will post, but I was hoping someone might be able to give me a more in depth explanation of the recursion, and how I would apply this to solving a maze. I'm not asking for anyone to write the code, I'm just hoping some explanations would put me on the right path. Thank you to anyone who answers.</p>
  
  <p><strong>Here are the examples I have:</strong></p>
  
  <pre><code>    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
  </code></pre>
  
  <p><strong>Here are the guidelines:</strong></p>
  
  <p>You are going to create a maze crawler capable of solving any maze you give it with the power of recursion!</p>
  
  <p>Question 1 - Loading the maze</p>
  
  <p>Before you can solve a maze you will have to load it. For this assignment you will use a simple text format for the maze. You may use this sample maze or create your own.</p>
  
  <p>Your objective for this question is to load any given maze file, and read it into a 2-dimensional list. 
  E.g.: loadMaze("somemaze.maze") should load the somemaze.maze file and create a list like the following...</p>
  
  <pre><code>    [['#','#','#','#','#','#','#','#','#'], 
       ['#','S','#',' ',' ',' ','#','E','#'], 
       ['#',' ','#',' ','#',' ',' ',' ','#'], 
       ['#',' ',' ',' ','#',' ','#',' ','#'], 
       ['#', #','#','#','#','#','#','#','#']] 
  </code></pre>
  
  <p>Note that the lists have been stripped of all '\r' and '\n' characters. In order to make the next question simpler you may make this list a global variable.</p>
  
  <p>Next write a function that prints out the maze in a much nicer format:</p>
  
  <p>E.g.,</p>
  
  <pre><code>    ####################################
      #S#  ##  ######## # #      #     # #
      # #   #             # #        #   #
      #   # ##### ## ###### # #######  # #
      ### # ##    ##      # # #     #### #
      #   #    #  #######   #   ###    #E#
      ####################################
  </code></pre>
  
  <p>Test your code with different mazes before proceeding.</p>
  
  <p>Question 2 - Preparing to solve the maze</p>
  
  <p>Before you can solve the maze you need to find the starting point! Add a function to your code called findStart() that will search the maze (character-by-character) and return the x and y coordinate of the 'S' character. You may assume that at most one such character exists in the maze. If no 'S' is found in the maze return -1 as both the x and y coordinates.</p>
  
  <p>Test your code with the 'S' in multiple locations (including no location) before proceeding.</p>
  
  <p>Question 3 - Solving the maze!</p>
  
  <p>Finally, you are ready to solve the maze recursively! Your solution should only require a single method: solve(y,x)</p>
  
  <p>A single instance of the solve method should solve a single location in your maze. The parameters y and x are the current coordinates   to be solved. There are a few things your solve method should accomplish. It should check if it is currently solving the location of the 'E'. In that case your solve method has completed successfully. Otherwise it should try to recursively solve the space to the right. Note, your method should only try to solve spaces, not walls ('#'). If that recursion doesn't lead to the end, then try down, then left, and up. If all that fails, your code should backtrack a step, and try another direction.</p>
  
  <p>Lastly, while solving the maze, your code should leave indicators of its progress. If it is searching to the right, the current location should have a '>' in place of the empty space. If searching down put a 'v'. If searching left '&lt;', and if searching up '^'. If your code has to backtrack remove the direction arrow, and set the location back to a ' '.</p>
  
  <p>Once your maze is solved print out the maze again. You should a see step-by-step guide to walking the maze.
  E.g.,</p>
  
  <pre><code>    main("somemaze.maze")
      ######### 
      #S#   #E# 
      # # #   # 
      #   # # # 
      #########
  </code></pre>
  
  <p>S is at (1,1) </p>
  
  <pre><code>     ######### 
       #S#&gt;&gt;v#E# 
       #v#^#&gt;&gt;^# 
       #&gt;&gt;^# # # 
       #########
  </code></pre>
  
  <p>Test your code with different different start and end locations, and optionally over a variety of mazes.</p>
  
  <p><strong>Here is the code I have so far:</strong>
  But the code is not actually printing the track in the maze, and I'm not sure why.</p>
  
  <pre><code>    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 &gt; len(mazeList) or x &gt; 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]= '&gt;'
          elif solve(x,y+1) == True:  #down
               mazeList[x][y]= 'v'     
          elif solve(x-1,y) == True:  #left
               mazeList[x][y]= '&lt;'     
          elif solve(x,y-1) == True:  #up
               mazeList[x][y]= '^'
          else:
             mazeList[x][y]= ' '
          return (mazeList[x][y]!= ' ')
  </code></pre>