Need help understanding recursion flow of this Python function

Question

I'm having difficulty understanding the recursion workflow of the following function and how it traverses through the array sorting the permutations.

One particular thing that's getting me stumped is how the 'return [nums[:]]' call behaves when it's in a recursive function. Since line 9 calls itself again until 'start == 2', when does it continue executing the lines past line 9 and for which of the recursive functions does it execute those proceeding lines?

Sorry if my question is a little confusing, I just started learning Python recently and would like to get a better understanding of how 'return' calls work in recursive functions. Any advice is appreciated!

class Solution(object):
  def _permuteHelper(self, nums, start=0):
    if start == len(nums) - 1:
      return [nums[:]]

    result = []
    for i in range(start, len(nums)):
      nums[start], nums[i] = nums[i], nums[start]
      result += self._permuteHelper(nums, start + 1)
      nums[start], nums[i] = nums[i], nums[start]
    return result

  def permute(self, nums):
    return self._permuteHelper(nums)

print(Solution().permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

`return` isn't a "call"; it's a *statement*. It is used to say what the result of the computation is. It works the same way in recursion that it does with any other function calling: the recursive call evaluates to some result, which is then used in the place where it was recursively called - exactly the same as if the call were not recursive. — Karl Knechtel, Oct 13 '20 at 02:13

score 0 · Accepted Answer · answered Oct 13 '20 at 02:07

Using a print statement is one of the best to analyze (for a beginner). You can run the below code to see exactly what is happening(I just inserted print statements at appropriate places).

class Solution(object):
    def _permuteHelper(self, nums, start=0):
        if start == len(nums) - 1:
            print('Returns: ',[nums[:]])
            return [nums[:]]
        result = []
        print("Start: ",start)
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            print("Swapped:", start," ", i)
            result += self._permuteHelper(nums, start + 1)
            nums[start], nums[i] = nums[i], nums[start]
        return result
    def permute(self, nums):
        return self._permuteHelper(nums)

print(Solution().permute([1, 2, 3])

Output:

Start:  0
Swapped: 0   0
Start:  1
Swapped: 1   1
Returns:  [[1, 2, 3]]
Swapped: 1   2
Returns:  [[1, 3, 2]]
Swapped: 0   1
Start:  1
Swapped: 1   1
Returns:  [[2, 1, 3]]
Swapped: 1   2
Returns:  [[2, 3, 1]]
Swapped: 0   2
Start:  1
Swapped: 1   1
Returns:  [[3, 2, 1]]
Swapped: 1   2
Returns:  [[3, 1, 2]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Need help understanding recursion flow of this Python function

1 Answers1