자료구조 - 재귀 함수

1. 재귀함수

재귀함수(Recursive Function)란 호출된 함수가 자기 자신을 다시 호출하는 풀이 방식이다. 실무에서는 성능 문제, 메모리 오버플로우 위험, 코드 가독성 저하 때문에 재귀 함수를 자주 쓰지 않는다. 하지만 커다란 문제를 쪼개 부분 문제로 만들어 해결함으로써 전체 문제를 풀어나가는 구조를 설계할 때 필요하기에 자료 구조나 알고리즘에서는 알아야 하는 필수 개념이다. 스택프레임과 지역변수의 역할을 알고나면 더 쉽게 이해할 수 있다.

 

1.1 재귀함수로 팩토리얼 구현

n팩토리얼은 1부터 n까지의 곱을 의미하고. n!라고 표기한다. 4!은 1*2*3*4를 의미한다. 4! = 3!*4로 풀어 쓸 수도 있다.

def factorial(n):
    return factorial(n-1) * n # 1

if __name__ == "__main__":
    for i in range(1, 6):
        print(factorial(i)) # 2

 

위의 코드는 최대 재귀 깊이를 초과하기 때문에 RecursionError가 발생한다. 그래서 아래처럼 제한조건을 정해야 한다.

def factorial(n):
    # base case
    if n <= 0: # 1
        return 1
    return n*factorial(n-1)

if __name__ == "__main__":
    for i in range(1, 6): 
        print(factorial(i))

 

1.2 스택 프레임으로 재귀함수 이해

함수가 호출되면 메모리에는 stack frame 공간이 생긴다. 이곳에는 함수 실행에 필요한 지역 변수들이 할당된다.

def add_two(a, b):
    c = a + b # 4
    return c

a = 10 # 1
b = 20 # 2
result = add_two(a, b) # 3
print(result)

 

• Python에서 변수는 “값을 담는 상자”라기보다 객체를 가리키는 이름(name binding) 이다.
• 함수가 호출되면 새 실행 프레임(frame) 이 만들어지고, 그 프레임에 매개변수/지역변수(로컬 이름) 가 관리된다.
• 호출 시 인자 전달은 “값 복사”가 아니라 객체 참조를 전달하고 로컬 이름을 그 객체에 바인딩하는 방식이다.
  • 불변 객체(int, str, tuple 등)는 수정이 안 되므로 복사처럼 보일 뿐이다.
  • 가변 객체(list, dict 등)는 같은 객체를 공유하므로 함수 안에서 변경하면 호출자도 영향을 받을 수 있다.
• 재귀는 호출할 때마다 새 프레임이 누적된다.
• 기저 사례(base case) 가 없거나 입력이 줄어들지 않으면 프레임이 계속 쌓여, Python에서는 보통 재귀 한도에 걸려 RecursionError가 발생한다.
• 재귀 설계의 핵심은 두 가지다.
  1. 입력을 어떤 규칙으로 줄여 결국 멈추게 만들 것인가
  2. 언제 멈출지(기저 사례) 를 명확히 정의했는가

 

1.3  순열을 재귀 함수로 구현하기 : 재귀 트리 사용하기

순열(permutation) 은 원소들의 순서를 바꾼 모든 경우의 수이며, 원소가 n개면 총 개수는 n!이다.

순열 문제는 “큰 문제를 작은 문제로 쪼개는” 전형적인 재귀 형태로 볼 수 있다.

핵심 아이디어: 현재 위치(start)에 올 원소를 하나씩 선택하고, 나머지 위치는 같은 방식으로 채운다.

 

재귀 호출이 의미하는 상태

• permutation(arr, start)는 보통 다음 의미로 정의한다.
  • arr[0:start] 구간은 이미 확정된 prefix
  • arr[start:] 구간은 아직 섞을 수 있는 후보들
• 함수가 호출될 때마다 새 실행 프레임(frame) 이 생기고, 그 프레임은 start, 루프 인덱스(idx) 같은 로컬 상태를 가진다.
• 여기서 중요한 점: arr는 리스트 객체 자체이므로, 재귀 호출로 “복사본”이 자동으로 생기지 않는다. 같은 리스트를 공유하면서 제자리(in-place)로 바꿔가며 경우를 만든다.

기저 사례(base case)

• start가 마지막 인덱스에 도달하면 더 이상 바꿀 자리가 없으므로, 그 시점의 arr는 완성된 순열이다.
  • 예: start == len(arr) - 1이면 출력/저장 후 반환.

swap → 재귀 → swap-back(백트래킹)

• 루프에서 idx를 start..끝까지 돌며:
  1. arr[start]와 arr[idx]를 교환(swap) 해서 “start 위치에 올 원소”를 하나 결정하고
  2. permutation(arr, start + 1)로 다음 자리를 재귀적으로 채운 뒤
  3. 재귀가 끝나면 swap-back으로 원상 복구한다.
• 이 원상 복구(swap-back) 가 없으면 다음 반복에서 배열 상태가 섞인 채로 남아 중복/누락이 발생한다.
  즉, 백트래킹의 본질은 “한 선택을 탐색한 뒤 상태를 되돌리고 다음 선택을 탐색하는 것”이다.

재귀 트리/스택 프레임 설명에서 주의할 점

• 재귀 트리의 각 노드는 “하나의 호출 상태”를 나타내며, 이를 “스택 프레임”이라고 설명하는 건 개념적으로 가능하다.
• 다만 이 코드에서는 {...} 같은 “부분집합을 새로 만들어 전달”하기보다는, 하나의 리스트를 공유하면서 start로 유효 구간을 좁히는 방식이다.따라서 “집합 크기가 줄어든다”라기보다, 고정된 prefix가 늘어난다가 더 정확한 표현이다.

def permutation(arr, start):
    if len(arr) - 1 == start: #start가 마지막 원소에 도달했을 때 섞을 다른 원소가 없으므로 완성된 순열 출력
        print(arr)
        return
    
    for idx in range(start, len(arr)):
        arr[start], arr[idx] = arr[idx], arr[start]
        permutation(arr, start+1)
        arr[start], arr[idx] = arr[idx], arr[start]

if __name__ == "__main__":
    arr = [1,2,3]
    permutation(arr, 0)