재귀 호출하는 함수 코드 2개 비교

• 종이를 이어 붙이는 모든 경우의 수를 탐색하는 재귀 호출

N = 5
# | ㅁ =
cnt = 0
def backtrack(n, paper):  # n의 종이의 길이
    if n == N:
        global cnt; cnt += 1
        print(cnt, paper)
        return

    # 길이 1인 종이
    backtrack(n + 1, paper + '|')
    if n + 2 <= N:
        # 길이 2인 사각형
        backtrack(n + 2, paper + 'ㅁ')
        # 길이 2인 눕혀서 만든 사각형
        backtrack(n + 2, paper + '=')

backtrack(0, '')

 

• 블랙잭 문제, 카드 3장을 뽑아서 M값에 가장 근접하는 카드 3장의 합을 찾는 코드

N, M = map(int,input().split())
arr = list(map(int,input().split()))

def dfs(level):
    global arr, N, lst, max_val,visited
    if sum(lst) > M:
        return
    elif level == 3:
        if max_val < sum(lst):
            max_val = sum(lst)
        elif max_val == M:
            return
        return
    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            lst.append(arr[i])
            dfs(level + 1)
            lst.pop()
            visited[i] = 0

lst = []
max_val = 0
visited = [0] * N
dfs(0)
print(max_val)

 

재귀 호출을 몇번 시키는 지만 다를 뿐 사실상 둘 다 DFS다!