재귀함수 (Recursive Function)

컴퓨터 과학에서 재귀한 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.

재귀함수란 함수안에 자신의 함수를 다시 호출하는 함수를 의미한다. 이러한 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다.

재귀함수의 구조

종료 조건(Base Case) : 더 이상 재귀가 필요하지 않을 때 종료하기 위한 조건. 없으면 무한 루프가 발생한다.

재귀 조건(Recursive Case) : 자기 자신을 더 작은 문제로 나누어 다시 호출하는 부분.

재귀 호출의 동작 방식

재귀 호출은 Call Stack을 기반으로 작동한다.

함수가 호출되면 현재 함수의 상태(지역 변수, 실행 위치 등)가 스택에 저장되고, 호출이 끝나면 이전 상태로 되돌아간다.

재귀 깊이가 깊어질수록 스택에 더 많은 프레임이 쌓인다.

Base Case에 도달하면 호출 순서의 역방향으로 반환값을 정리한다.

재귀의 활용

수학적 정의 기반 문제들은 팩토리얼, 피보나치, 하노이의 탑등

자료구조 탐색은 트리, 그래프(DFS)

분할 정복 알고리즘은 퀵 정렬, 합병 정렬

재귀의 장단점

장점은 코드가 간결해지고, 직관적으로 변하며, 반복문 보다 깔끔해서 특정 문제에 특화되어 있다.

단점은 성능 저하 왜냐하면 호출시마다 스택을 사용하고, 오버헤드가 발생한다. 호출흐름이 복잡해지면 추적이 어렵다. 메모이제이션이 없으면 비효율적이다. 재귀가 깊어지면 메모리 한계를 넘길 수 있다.

재귀와 반복문 차이

반복문은 상태를 루프 내에서만 직접 관리하고, 재귀는 상태 호출 스택을 통해 암묵적으로 관리함.

재귀 최적화 개념

메모이제이션은 중복 호출을 방지하는 것

DP는 하위 문제의 결과를 저장하는 것

꼬리 재귀는 마지막에 자기 자신을 호출하는 것 → 컴파일러가 반복문으로 최적화가 가능.

예제

팩토리얼 계산 문제

자연수 N이 주어졌을 때, N! 팩토리얼을 재귀함수로 계산하라.

N! = N x (N-1) x (N-2) x … x 1 여기에서 0! = 1이다.

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

print(factorial(5)) # 출력은 5*4*3*2 = 120이 나온다.

재귀로 문자열 뒤집기

문자열이 주어졌을 때, 재귀를 사용하여 문자열을 뒤집어라.

입력에 abc 넣었을 때 출력이 cba가 나올 수 있게끔.

def reverse_string(s):
	if s == "": 
		return s
	return reverse_string(s[1:]) + s[0] # recursive case
print(reverse_string("hello")) # 출력은 'olleh'

bc + a, c + b, + c 이렇게 하고 기다리다가 마지막에 종료 조건 만나서 끝났다가, 다시 거꾸로 조립을 해야 하지.

처음에는 아무것도 없음.

• c ⇒ c, c+ b ⇒ cb, cb + a ⇒ cba 이런식으로 최종적으로 합쳐짐.

결국 다 돌고서 s를 리턴을 쭈욱 하잖아. s[0]에 있는 것과, s[1]에 있는 거

백트래킹 (Backtracking)

해를 찾는 과정에서 안 되는 길은 빨리 포기하고 되돌아가는 탐색 방법이다. 이름 그대로 뒤로 돌아가면서 다시 탐색하는 방식.

가능한 모든 해를 탐색하되, 해가 될 수 없는 경우는 더 이상 진행하지 않고 중단.

백트래킹의 동작 원리

해 탐색 : 모든 가능한 경우의 수를 탐색.

가지치기 : 현재 탐색 중인 경로가 해가 될 가능성이 없으면 그 경로를 중지하고 이전 단계로 돌아갑니다.

구조(보통 DFS + 조건검사)

현재 상태가 유요한지 검사.

유요하다면 다음 단계(자식 노드)로 진행 (재귀 호출)

유효하지 않으면 바로 종료하고 이전 단계로 백트래킹

재귀 호출 이후

N-Queen

각 행마다 퀸을 하나씩 놓되, 서로 공격하지 않게(같은 열/대각선은 불가)

안 되는 곳이면 바로 다음 열로 넘어간다.(가지 치기)

def is_safe(board, row, col): # 안전한 위치인지 확인함.
    for i in range(row):
        # 같은 열에 퀸이 있거나
        if board[i] == col:
            return False
        # 대각선에 퀸이 있으면 안 됨 (행 차이 == 열 차이)
        if abs(board[i] - col) == row - i:
            return Fals
    return True

def solve_n_queens(board, row): # 행을 하나씩 돌면서 퀸을 놓는다
    if row == len(board): # 퀸을 모든 행에 다 놓았으면 성공
        print(board)
        return True
        
    for col in range(len(board)):# 현재 row에서 가능한 모두 확인
        if is_safe(board, row, col):
            board[row] = col # 실질적으로 퀸 놓음
            solve_n_queens(board, row + 1) # 다음행 넘어감.
            board[row] = -1  # 백트래킹