Returning a list of lists using python recursion

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.