Questions about Python Recursive Functions

Asked 2 years ago, Updated 2 years ago, 70 views

Recently, I am studying algorithms using Python in letcode. I am studying the code to perform permutation as shown below, but there is something I don't understand in the middle.

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results, prev_elements = [], []

        def dfs(elements):
            print(f' # elements: {elements} # prev_elements: {prev_elements}')
            # Why len(elements) == 0: The length of the next_elements given by the dfs factor is leaf no\
This is because the length decreases by 1 until de.                                                 
            If len(elements) == 0: # Add result when leaf node (Exception handling)                    
                results.append( prev_elements[:] )

            for e in elements:
                print(f'e: {e}')
                # All elements are delivered to the next spot for delivery on the next tour.            
                next_elements = elements[:]                                 
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements)

                # When looking at the position of the dash line of the output result, it is output after elements=[].    
                # -> Until then, you can see that dfs is recursively called.                               
                print('- ' * 15)                                                
                prev_elements.pop()
                print(f'poped prev_elements: {prev_elements}')
                print('>' * 50)

        dfs(nums)

        return results

nums = [1, 2, 3]
_solver_obj = Solution()
results = _solver_obj.permute(nums)
print(results)

If you perform the above permutation code, it will be printed as follows. (If you don't understand, I'm sorry that I tend to print it out one by one.)

 # elements: [1, 2, 3] # prev_elements: []
e: 1
 # # elements: [2, 3] # prev_elements: [1]
e: 2
 # # elements: [3] # prev_elements: [1, 2]
e: 3
 # # elements: [] # prev_elements: [1, 2, 3]
- - - - - - - - - - - - - - - 
poped prev_elements: [1, 2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
 # # elements: [2] # prev_elements: [1, 3]
e: 2
 # # elements: [] # prev_elements: [1, 3, 2]
- - - - - - - - - - - - - - - 
poped prev_elements: [1, 3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 2
 # # elements: [1, 3] # prev_elements: [2]
e: 1
 # # elements: [3] # prev_elements: [2, 1]
e: 3
 # # elements: [] # prev_elements: [2, 1, 3]
- - - - - - - - - - - - - - - 
poped prev_elements: [2, 1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
 # # elements: [1] # prev_elements: [2, 3]
e: 1
 # # elements: [] # prev_elements: [2, 3, 1]
- - - - - - - - - - - - - - - 
poped prev_elements: [2, 3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 3
 # # elements: [1, 2] # prev_elements: [3]
e: 1
 # # elements: [2] # prev_elements: [3, 1]
e: 2
 # # elements: [] # prev_elements: [3, 1, 2]
- - - - - - - - - - - - - - - 
poped prev_elements: [3, 1]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
e: 2
 # # elements: [1] # prev_elements: [3, 2]
e: 1
 # # elements: [] # prev_elements: [3, 2, 1]
- - - - - - - - - - - - - - - 
poped prev_elements: [3, 2]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: [3]
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- - - - - - - - - - - - - - - 
poped prev_elements: []
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The part that I don't understand is the part where the dash line is output and the popped prev_elements are output. I don't understand why prev_elements.pop() is so many times. I wonder which code makes this happen. Thank you

python recursive

2022-09-20 19:09

1 Answers

You can also try running vs code in debugging mode. I think it's best to run it in debugging mode and follow it.

If you want to see the log, it's better to see the depth of the recursive function together. I believe it will be helpful if you add a parameter called depth and log it and look at the results and think about it.

from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results, prev_elements = [], []

        def dfs(elements, depth=0):
            print("  "*depth + f" # elements: {elements} # prev_elements: {prev_elements}")
            # Len(element) == 0 because the length of the next_element given by the dfs factor decreases by 1 until the length of the next_element becomes the leaf node.
            If len(elements) == 0: # Add result when leaf node (Exception handling)
                results.append(prev_elements[:])

            for e in elements:
                print("  "*depth + f"e: {e}")
                # All elements are delivered to the next spot for delivery on the next tour.
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements, depth+1)

                # When looking at the position of the dash line of the output result, it is output after elements=[].
                # -> Until then, you can see that dfs is recursively called.
                print("  "*depth + "- " * 15)
                prev_elements.pop()
                print("  "*depth + f"poped prev_elements: {prev_elements}")
                print("  "*depth + ">" * 50)

        dfs(nums)

        return results


nums = [1, 2, 3]
_solver_obj = Solution()
results = _solver_obj.permute(nums)
print(results)


2022-09-20 19:09

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.