Returning a list of lists using python recursion

Question

I'm brushing up on recursion problems and have no issues when the problem statement asks to print values (eg. BST traversal where you print the node values), and similarly few issues when the problem asks to return a list of values (return a path between 2 nodes in a tree) but am having problems when there are multiple answers, involving multiple lists (or a single 2D list) to be returned. For example the problem asks me to return how many ways a child can reach the top of the stairs, assuming it can jump either 1, 2, or 3 steps at a time. This is no problem and is solved below

def step_helper(steps):
    if(steps == 0):
        return 1
    elif(steps < 0):
        return 0
    else:
        return step_helper(steps-1) +
             step_helper(steps-2) + 
             step_helper(steps-3)

def find_num_ways(steps):
    count = step_helper(steps)
    print(count)

find_num_ways(10)

Similarly if I need to return a path from two nodes in a BST, returning 1 list is no problem

def another_path_helper(self, n1, n2):
    if(n1 == None):
        return [None]
    elif(n1 == n2):
        return [n1.data]
    elif(n1.data > n2.data):
        return [n1.data] + self.another_path_helper(n1.left, n2)
    elif(n1.data < n2.data):
        return [n1.data] + self.another_path_helper(n1.right, n2)
    else:
        return None

def another_path(self, n1, n2):
    path = self.another_path_helper(n1, n2)
    if(None in path):
        return None
    else:
        return path

However, I'm clueless on how I would return a list of lists. In the child-steps example, instead of returning the number of ways a child can climb the stairs, how could I return a list of paths, which would be a 2d list, where each entry would be a list of steps taken to get from bottom to top? Ideally I would not need to pass a list as argument to my recursive function since I've been told passing mutable objects to recursive functions is a bad practice and no different from using a static counter.

Answer 1

There is absolutely nothing wrong with passing a list as an argument to your recursive function, and not modifying it. In fact, doing so makes it fairly trivial to solve the problem.

Consider a small version of the problem: only 3 steps. You are at the bottom of the stairs. You can take one step, two steps or three steps. You then have 3 sub-problems to solve:

• All the solutions starting with a path of [1], going 2 additional steps.
• All the solutions starting with a path of [2], going 1 additional step.
• All the solutions starting with a path of [3], going 0 additional steps.

Looks like a good start towards the recursive solution.

Let's focus on just the first of these sub-problems. Your path is [1], and you have 2 addition steps to go. From here, you can take 1 step, 2 steps or 3 steps. You again have 3 sub-sub-problems:

• All the solutions starting with a path of [1,1], going 1 additional step.
• All the solutions starting with a path of [1,2], going 0 additional step.
• All the solutions starting with a path of [1,3], going -1 additional steps.

The first sub-sub-problem requires more work ... another recursive call, which should return [[1,1,1]]. The second sub-sub-problem should return just the path we've taken to get here: [[1,2]]. And the last sub-sub-problem should return no solutions: []. We add these solutions together [[1,1,1]] + [[1,2]] + [] to get [[1,1,1],[1,2]], and return that.

Backing up, the second sub-problem, "starting with a path of [2], going 1 additional step" should return [[2,1]] as the set of solutions. The third sub-problem, "starting with a path of [3], going 0 additional steps" should return [[3]]. Adding these solutions together with [[1,1,1],[1,2]] gives the complete solution set: [[1,1,1],[1,2],[2,1],[3]]

As code:

def find_paths(total):

   def helper(path, remaining):
      paths = []
      if remaining == 0:
         paths.append(path)
      elif remaining > 0:
         for step in range(1,3+1):
            paths.extend( helper(path + [step], remaining - step))
      return paths

   return helper([], total)

print(find_paths(3))

The output, as expected, is:

[[1, 1, 1], [1, 2], [2, 1], [3]]

---

Of course, you don't have to pass path, the current list of the steps, into the recursive call. You could instead just ask for all paths from the current step to the top of the stairs, and prefix those with the step just being taken. We don't even need a helper in this case:

def find_paths(remaining):

   paths = []
   if remaining == 0:
      paths.append([])
   for step in range(1,3+1):
       if step <= remaining:
          subpaths = find_paths(remaining - step)
          for subpath in subpaths:
             paths.append([step] + subpath)

   return paths

print(find_paths(4))

The output, as expected, is:

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]

It should be noted that find_paths(2) will be called -- and will return the same subpaths, [[1,1], [2]] -- after ascending the first two steps, either one at a time with the path [1,1] or as one jump of two steps with the path [2]. Since it returns the same value, instead of recomputing all the subpaths from that point, we can cache the result, and reuse the value on subsequent steps.

from functools import lru_cache

@lru_cache()
def find_paths(remaining):

   paths = []
   if remaining == 0:
      paths.append([])
   for step in range(1,3+1):
       if step <= remaining:
          subpaths = find_paths(remaining - step)
          for subpath in subpaths:
             paths.append([step] + subpath)

   return paths

paths = find_paths(10)
print(len(paths))
print(find_paths.cache_info())

274
CacheInfo(hits=17, misses=11, maxsize=128, currsize=11)

If you set the cache size to zero @lru_cache(maxsize=0), you can see that the find_paths() function is called 600 times in the course of the problem: CacheInfo(hits=0, misses=600, maxsize=0, currsize=0). With the cache enabled, it is called only 28 times, and only executes 11 times; 17 times, the previously stored result is immediately returned, which can be a considerable savings.