In a recursive call, how does memory / call stack inside the function itself behave for this given example

Question

totalcount = 0
res = []

def permute(nums):
    backtrack(nums, [])

def backtrack(nums, path):
    global totalcount
    totalcount += 1
    if not nums:
        res.append(path)
    for x in range(len(nums)):
        #res.append(x)
        backtrack(nums[:x]+nums[x+1:], path+[nums[x]])

permute([1,2,3])

This is the code to return the permutations of a list of numbers, in my case [1, 2, 3]. I'm trying to trace the recursive calls to view the logic flow, but I just can't wrap my mind around it. When I commented in res.append(x) to figure out why I see this:

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

Also totalcount is 16 here, and I'm not sure why this function ran a total of that many times.

My questions are :

1. When backtrack is called for the first time, x=0. but of course it calls backtrack again, so in those calls, x goes to zero again. Following nums[:x]+nums[x+1:], path+[nums[x]] in this logic, I can see where [1,2,3] comes from (and before [1,2,3] the x values are 0,0,0 as I expected). But then all those inner calls should finish and then X should be two right? so doesn't that mean the next item in res should be [2,1,3]? I would expect this to just output res = [1,2,3],[2,1,3],[3,1,2], but it is indeed correctly giving the remaining permutations where 1 is first and 2 is first and 3 is first. How?
2. Why are there sometimes 3 instead of 2 values before a permutation set? Why are the values what they are? I suppose if I could understand these things I would understand a lot more about recursion and backtracking, but I've been trying to trace this out on paper for a long time and I am getting no closer.
3. What is the true order of these calls? if it runs 16 times, what are the values of the different variables in it on those runs?

Answer 1

Rather than answer your questions, I hope I can give you a technique that will let you find the answers for yourself. Consider adding a breakpoint() call to your code. It's a built-in that will put you in the interactive debugger.

totalcount = 0
res = []
def permute(nums):
    backtrack(nums, [])
def backtrack(nums, path):
    global totalcount
    totalcount += 1
    if not nums:
        res.append(path)
    for x in range(len(nums)):
        #res.append(x)
        backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
breakpoint()
permute([1,2,3])

Once you are in the interactive debugger, you can use the h command to list the available commands or h <command> to get help on a command. Basically, you need to just use the s command to step through your code.

Is there a way to determine which calls are a result of which?

The debugger can definitely help you with that. Here are more commands that could help you:

1. where (w) - provided a stack trace
2. up (u) - change stack frame to calling function
3. down (d) - opposite of up
4. print (p) - display variable contents (but you can just use variable name if it doesn't collide with pdb commands )

With that information, you can display the local variables in the calling function to give you an idea of where you were in the process:

$ python back
> /Users/mrosen609/fun/back(15)<module>()
-> permute([1,2,3])
(Pdb) b 13
Breakpoint 1 at /Users/mrosen609/fun/back:13
(Pdb) c
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) w
  /Users/mrosen609/fun/back(15)<module>()
-> permute([1,2,3])
  /Users/mrosen609/fun/back(5)permute()
-> backtrack(nums, [])
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) c
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) w
  /Users/mrosen609/fun/back(15)<module>()
-> permute([1,2,3])
  /Users/mrosen609/fun/back(5)permute()
-> backtrack(nums, [])
  /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) nums
[2, 3]
(Pdb) nums, path
([2, 3], [1])
(Pdb) up
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) nums, path
([1, 2, 3], [])
(Pdb) x
0
(Pdb) down
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) nums, path
([2, 3], [1])
(Pdb) x
0
(Pdb) c
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) w
  /Users/mrosen609/fun/back(15)<module>()
-> permute([1,2,3])
  /Users/mrosen609/fun/back(5)permute()
-> backtrack(nums, [])
  /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
  /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) x
0
(Pdb) nums, path
([3], [1, 2])
(Pdb) up
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) nums, path
([2, 3], [1])
(Pdb) up
> /Users/mrosen609/fun/back(13)backtrack()
-> backtrack(nums[:x]+nums[x+1:], path+[nums[x]])
(Pdb) nums, path
([1, 2, 3], [])

To be honest, I did introduce two additional commands: (b) breakpoint and (c) continue. I wanted let the program run until it hit line 13 and not have to press (s) step so much. And so, ideally you can see that (c) continue takes you to the next breakpoint.

Hopefully this example helps, but you may want to review the interwebs for additional information about pdb.

Answer 2

I logged the calls:

backtrack([1, 2, 3], [])
    backtrack([2, 3], [1])
        backtrack([3], [1, 2])
            backtrack([], [1, 2, 3])
        backtrack([2], [1, 3])
            backtrack([], [1, 3, 2])
    backtrack([1, 3], [2])
        backtrack([3], [2, 1])
            backtrack([], [2, 1, 3])
        backtrack([1], [2, 3])
            backtrack([], [2, 3, 1])
    backtrack([1, 2], [3])
        backtrack([2], [3, 1])
            backtrack([], [3, 1, 2])
        backtrack([1], [3, 2])
            backtrack([], [3, 2, 1])

Obtained with this decorator:

def log(func):
    depth = 0
    def logging_func(*args):
        nonlocal depth
        print('    ' * depth +
              func.__name__ + '('+
              repr(args)[1:-1] + ')')
        depth += 1
        result = func(*args)
        depth -= 1
        return result
    return logging_func

Just copy that into your code and apply it to your backtrack:

@log
def backtrack(nums, path):
    ...

Try it online!