재귀를 이해하기위한 노력

재귀란 함수를 반복 호출해서 간결한 코드로 반복되는 문제를
해결하는 것을 말한다.

납득은 했지만 글쎄?

뭔가 재귀를 활용한 결과물을 읽는 것은 괜찮았으나
막상 이걸 응용해서 코드를 작성해보라고 하면 막혔었다.
그래서 제대로 이해를 못한 것 같다고 판단했고
크래프톤 정글에서 같이 공부하는 학우의 추천으로
쉬운 재귀 문제인 'N과 M'을 풀고 재귀를 조금이라도 더 이해해보기로 했다.
https://www.acmicpc.net/problem/15649

백준 15649

import sys
input = sys.stdin.readline

def dfs():
    # 재귀 종료 조건 
    if len(stack)==M:
        # 재귀 종료시 수행할 연산
        print(" ".join(map(str,stack)))
        return
    # 반복 탐색
    for i in range(1,N+1):
        # 탐색 판단 조건 (계속 탐색할지 넘어갈지)
        if visited[i]:
            continue
        # 반복할 때 실행할 연산 -> 자식 노드로 간다.
        visited[i] = True
        stack.append(i)
        # 재귀 함수
        dfs()
        # 조건이 맞지 않아 백트래킹시 할 연산 -> 부모 노드로 간다. 
        visited[i] = False
        stack.pop()

N,M = map(int, input().split())
stack = []
visited = [False]*(N+1)
dfs()

-> 이미 다른 누군가 작성한 코드를 바탕으로
각 부분이 하는 역할을 주석으로 작성했다.
풀었던 재귀문제 중에서 거의 처음으로 머릿속에서 짤 수 있는
간단한 코드였다.

포인트

재귀를 이해하기 위해서
각 코드가 부분적으로 하는 역할을 비교해봤다.

def dfs():
    # 재귀 종료 조건 
    if 탐색을 마무리해 답을 찾았다면:
        # 재귀 종료시 수행할 연산
        # 함수 종료 return
        
    # 반복 탐색
    for i in 탐색할 범위:
        # 탐색 판단 조건 (계속 탐색할지 넘어갈지)
        if 답이 될 수 없다면:
            # 다음으로 continue
        # 반복할 때 실행할 연산 -> 자식 노드로 간다.
        # 재귀 함수
        # 조건이 맞지 않아 백트래킹시 할 연산 -> 부모 노드로 간다.