How to use recursion for "for" loops-CodePudding

My code is meant to find the longest path in a matrix, where each value is greater than the one previous. However, I've been instructed to not use for loops at all, which is difficult because I have 3, with 2 of them being involved in a nested loop. Is there any way I could only user recursion to solve this?


  def path(self, matrix):

    res = 1
    
    # for loop to run the function for every element in list
    for row in range (len(matrix)):
      for col in range (len(matrix[0])):
        # pass in the current max and the new spot, and take the max value
        res = max(res, self.dfs(matrix, row, col))

    # return the max value
    return res

  # function to compare paths (Depth-First Seach)
  def dfs(self, matrix, row, col):
    # if spot was visited before, return value from cache
    if (row, col) in self.cache:
      return self.cache[(row, col)]

    # Set a default value of 1
    self.cache[(row, col)] = 1

    # moving the tile of focus
    for rowVal, colVal in self.directions:
      newRow = row   rowVal
      newCol = col   colVal

      # if the pointer can move in a direction (not out of bounds), and is greater: store cache value
      if (0 <= newRow < len(matrix)) and (0 <= newCol < len(matrix[0])) and matrix[row][col] < matrix[newRow][newCol]:
        self.cache[(row, col)] = max(self.cache[(row, col)], 1   self.dfs(matrix, newRow, newCol))

CodePudding user response：

Recursion is about a base case and an iterative case. In your situation, think of the smallest matrix you can - an empty matrix. That is your base case. Your function should return a path length of 0 if it is empty.

The iterative case is a bit more difficult, and usually where things become confusing. The key goal of the iterative case is to reduce the size of the problem, usually by the smallest amount possible.

To overly simplify, if you start with a function like this:

def f(ls):
    for x in ls:
        result = g(x, result)
    return result

Then the iterative version looks like this:

def f(ls, result):
    if 0 == len(x):  # Base Case
        return result
    else:  # Iterative Case
        result = g(x, result)
        return f(ls[1:], result)

The trick is figuring out what of your internal logic goes into g() and how to represent the result.

Let's take a simpler version of your problem, where we deal with a single array and want to return the longest 'path' in that array. A path is a sequence of integers that are incrementing by one.

So, if we have [0,1,2,3] the expected value is 4. If we have [0,1,1,2,3] the expected value is 3. Similarly, 3 would be expected for the input [0,1,2,2,1]. [3,2,1] should return 0.

The most basic signature we require is this:

def f(ls: list[int]) -> int

Essentially, 'a function that takes a list of ints and returns the length of the longest path'. But we have to remember a bit of extra state to do this properly. Specifically, we need to remember the length of the current path we are on, and the lengths of all paths we have found.

def f(ls: list[int], current_path: int) -> int

Let's examine the base case. A base case is any case where reducing the size of your input (in our case 'input' really refers only to ls) would not yield an easier problem to solve. There are two base cases - if the input list is length 0 or 1. In both these cases, we have no need to shrink the problem any further.

def f(ls: list[int], current_path: int) -> int:
    # If there are no elements, current_path is the only valid length
    if 0 == len(ls):
         return current_path
    # If there is one element, increment current_path before returning it, to account for the length that element adds
    if 1 == len(ls):
         return current_path   1

These serve to terminate the recursion. Now lets look at the iterative case:

def f(ls: list[int], current_path: int) -> int:
    # Base cases
    if 0 == len(ls):
        return current_path
    if 1 == len(ls):
        return current_path   1
    # Iterative case - guaranteed that len(ls) >= 2
    current_path = current_path   1  # Increment the current_path to account for the current element.
    if ls[1] == ls[0]   1:
        # In this branch we know that the path will continue.
        return f(ls[1:], current_path)  # ls[1:] reduces our problem space by one element
    else:
        # In this branch the path ends, because the next element breaks the incremental sequence.
        recursive_result = returnf(ls[1:], 0)  # Reduce the problem space and start a new path of length 0
        return max(recursive_result, current_path)  # Choose which path is longer

There is a lot going on here, so I'll break it down in parts. The key thing to remember is that we are going to reduce the problem space - shorten the list - and then recurse with that smaller problem space. The element we are removing is therefore key to determining how we proceed.

Since we are removing one element, we add one to the current path. If the incoming path length was 0, we now have a path length of 1. If it was 3, we now have a path of 4.

Then we check the value of the next element. Is it exactly larger than the current element? If so, we know the path will continue, so we recurse, passing along a list without the current element and the length of our current path.

If it is not exactly one more, we know our current path ends here. In the recursion we pass along a new path length of 0, resetting the counter. But we have to do something with the returned value - decide whether it is larger than the current path as it stands at this element. Hence using max() to choose between the two possibilities.

This gives you a recursive function that iteratively shortens the problem at each step until it finds a base case, at which point it returns - but it returns up through the recursive function, accumulating the results.

(n.b. There are ways to optimize this, clean it up, add default values, etc. I'm skipping that because it doesn't help you think about the recursion.)

Your actual problem is harder. You're going along a two dimensional array. The key insight to have is this: in the iterative step in the example I gave, I looked at all the possible cases for moving forward and chose between them. However, you can go down all possible paths. If you are at a particular element in a two dimensional array, you know that you can go one way or the other - that's two recursive function calls. Because recursion is shortening your problem space, your iterative step can simply trust it will return, and only deal with the results. In your case, that is choosing which of the two recursive calls you made returned the larger result.

(At this point I have to make assumptions about your problem because you included neither a complete specification nor full code.)

def f(matrix: list[list[int], coords: (int, int), current_path: int) -> int:
    # Find all possible 'next steps'. For a next step to be valid it must be exactly one greater than the current location.
    # Base Case - There are no possible next steps -> return current path   1
    # Increment path
    # Iterative cases
        # There is only one next step -> recurse passing new coordinates and path length
        # There are two or three next steps -> recurse passing new coordinates and path length, then choose which result is the longest.

The difficulty here is that this finds the longest path from any given starting position. To truly find the longest path in the matrix, you would have to add a fourth argument to your function - a list of all the starting positions you have tried. Then you would change your logic for finding the next steps from 'is it strictly one larger' to 'is it strictly one larger or have I not tried starting from that point'?

# Use type aliases so you're clear about the types
type Matrix: list[list[int]]
type Coordinate: (int, int)  # x-y coordinates
type Cache: list[Coordinate]  # All the places we've started from

def f(matrix: Matrix, 
      coords: Coordinate, 
      current_path: int, 
      starting_points: Cache) -> int:
    if 0 == len(matrix):
      return current_path
    if 1 == len(matrix) and 0 == len(matrix[0]):
      return current_path
    current_path = current_path   1  # From here on, we have a valid element at this coordinate
    if 1 == len(matrix) and 1 == len(matrix[0]):
      return current_Path
    moves = get_all_moves(...)
    if 0 == len(moves):  # This is *also* a base case - the problem cannot be shrunk any further!
      return current_path
    results = try_each_move(moves)  # This is also a recursive function... but a *different* recursive function, in order to avoid using a for loop (or list comprehension)
    return max(max(results), current_path)

A few closing notes:

Do try to adhere to python style guides. It makes reading python easier!
Any information you think you need to store outside the function can just be passed as a parameter. Pure recursive functions don't have access to a closure or outer scope. Depending on your case, this may not be the most efficient solution, but it is where you should start until you're much more comfortable with recursion.
Similarly, if copying a value rather than a reference makes it easier for your to reason about what you're doing, do that first. Efficiency is for later. Clarity first.
Recursion often (though not always) easier if you're building up a solution from the return of the recursion call. In the examples here, the max() function is doing that accretion, but you could imagine inverting the approach here and first doing the recursive call, which returns two values - the value of the last element and the length of the path. Then you could decide if you're smaller than that value. I didn't do that here because you'd have to remember two path lengths at a time.
In this specific problem, do take care with the cache. You can't just remember if you've ever visited a coordinate.

CodePudding user response：

Recursion is just a function that keeps calling itself until it reaches a condition that disallows it from continuing.

Here's an example that's themed toward your needs.

""" Emulation Of:
for row in range (len(matrix)):
    for col in range (len(matrix[0])):
        print(matrix[row][col])
"""

matrix = [[1,2,3],[4,5,6],[7,8,9]]

#wrapping everything in this function makes `i` unreachable
#because it should be managed internally
def process_matrix(r:int, c:int) -> None:
    
    def columns(i:int=0, r:int=0) -> None:
        if i==c: return     #columns finished
        print(matrix[r][i]) #work
        columns(i 1, r)     #next column

    def rows(i:int=0) -> None:
        if i==r: return     #rows finished
        columns(0, i)       #recurse all columns for this row
        rows(i 1)           #next row
        
    rows(0)                 #start recursion

#use    
process_matrix(len(matrix), len(matrix[0]))

If you are trying to retrieve data, you have to return the "recursion call". Otherwise, you'll get None back from the very first call, and the recursion will carry on in a way that is unreachable by your code.

data = [10,20,30,40,50,60]   

def where_is_50(i:int=0) -> int:
    if data[i] == 50:
        return i            #stop recursion
    return where_is_50(i 1) #next
 
print(where_is_50())

If it isn't clear, The first time the function is called, it is not 50 so, it returns a call to itself. However, the actual return can't finish until the call does. Essentially, you end up with a string of "active" functions that are all waiting for the call that finds 50. When 50 is found, the return value keeps ascending through all the calls back to the very first one.

Whatever recursive functions you make should have a local reference to the data to traverse. In other words, don't pass your entire matrix on each call. Pass names or indexes recursively.