파이썬 재귀 함수 관련 질문
조회수 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
댓글 입력