파이썬 재귀 함수 관련 질문

조회수 457회

최근 leetcode에서 파이썬을 이용한 알고리즘을 공부하고 있습니다. 아래와 같이 permutation을 수행하는 코드를 공부하고 있는 데 중간에 이해가 되지 않는 부분이 있습니다.

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}')
            # len(elements) == 0이 되는 이유: dfs 인자로 주는 next_elements의 길이가 leaf no\
de가 될 때까지 길이가 1씩 감소하기 때문이다.                                                 
            if len(elements) == 0:  # leaf node일 때 결과 추가(예외 처리)                    
                results.append( prev_elements[:] )

            for e in elements:
                print(f'e: {e}')
                # 다음 순회 때 전달해주기 위해 다음 자리에 올 element을 전해준다.            
                next_elements = elements[:]                                 
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements)

                # 출력한 결과의 dash line의 위치를 보면 elements=[]이 된 이후에 출력된다.    
                # -> 그 전까지 dfs가 재귀 호출됨을 볼 수 있다.                               
                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)

위와 같은 permutation을 수행하는 코드를 수행하면 아래와 같이 출력이 됩니다. (이해가 안 되면 하나씩 출력하는 취향이라 긴 죄송합니다.)

 # 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]]

제가 이해가 안 가는 부분은 dash line이 출력되고 poped prev_elements가 출력되는 부분입니다. 저는 왜 prev_elements.pop()이 여러 번 되는 지 이해가 가지 않습니다. 어느 코드에서 이러한 수행되도록 하는지 궁금합니다. 감사합니다

  • (•́ ✖ •̀)
    알 수 없는 사용자

1 답변

  • vs code 도 디버깅모드로 실행해 볼 수 있습니다. 디버깅모드로 실행하며 따라가 보는 게 가장 좋을 것 같고요.

    로그를 달아서 보고 싶다면, 재귀함수의 경우는 재귀의 깊이를 같이 보는 게 이해가 더 좋아요. 다음처럼 depth 라는 parameter 를 추가해서 로깅을 해서 결과를 보고 생각을 해 보면, 도움이 되리라 믿습니다.

    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(elements) == 0이 되는 이유: dfs 인자로 주는 next_elements의 길이가 leaf node가 될 때까지 길이가 1씩 감소하기 때문이다.
                if len(elements) == 0:  # leaf node일 때 결과 추가(예외 처리)
                    results.append(prev_elements[:])
    
                for e in elements:
                    print("  "*depth + f"e: {e}")
                    # 다음 순회 때 전달해주기 위해 다음 자리에 올 element을 전해준다.
                    next_elements = elements[:]
                    next_elements.remove(e)
    
                    prev_elements.append(e)
                    dfs(next_elements, depth+1)
    
                    # 출력한 결과의 dash line의 위치를 보면 elements=[]이 된 이후에 출력된다.
                    # -> 그 전까지 dfs가 재귀 호출됨을 볼 수 있다.
                    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)
    
    • 안녕하세요. 수정해주신 코드를 실행했더니 prev_elements.pop() 라인이 실행하면 depth가 3 -> 2로 다시 올라가는데 혹시 그 이유를 알려주실 수 있으신가요? 혹은 사전 지식이 필요하면 해당 지식에 대한 키워드를 알려주시면 검색해서 공부하겠습니다. 감사합니다. ps. vs code debugging mode에 알려주셔서 감사합니다. 알 수 없는 사용자 2021.1.8 20:45

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)