재귀
재귀(Recursion)는 함수가 자기 자신을 호출하는 것을 의미한다.재귀 함수는 재귀 호출을 반복하여 문제를 해결한다.
재귀적인 접근은 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제의 결과를 결합하여 원래 문제를 해결하는 방식이다.
재귀 함수는 보통 다음과 같은 형태를 가진다:
def recursive_function(...):
if base_case_condition:
return base_case_result
else:
# 하위 문제로 분할하여 재귀 호출
result = recursive_function(...)
# 결과 결합 또는 처리
return result-
탈출 조건을 확인한다.
탈출 조건이 충족되면, 재귀 호출 없이 바로 결과 값을 반환한다. 반대로 말하면 탈출조건이 충족되지 않으면 재귀함수는 무한 반복하게 되니 주의하자. -
탈출 조건이 충족되지 않은 경우, 재귀 호출을 수행하여 문제를 더 작은 하위 문제로 분할한다.
재귀 호출된 하위 문제들의 결과를 결합하거나 처리하여 원래 문제의 해답을 얻는다. -
탈출조건 또는 조건을 만족할 경우 해답을 반환한다.
재귀 함수는 호출할 때마다 함수의 호출 정보와 지역 변수 등을 저장하는 스택을 사용한다. 이로 인해 재귀 호출이 너무 깊어지면 스택에 너무 많은 프레임이 쌓이게 되어 스택 오버플로우(Stack Overflow)가 발생할 수 있다. 또한, 같은 하위 문제를 반복해서 해결하게 되므로 중복된 계산이 발생할 수 있다.
이러한 문제를 해결하기 위해 동적 계획법(Dynamic Programming) 등의 기법을 적용하여 재귀 호출을 반복문으로 변경하는 것이 좋은 방법이다. 동적 계획법은 하위 문제의 결과를 저장하고 재활용하여 중복 계산을 피하는 기법이다.
하지만 정글1주차에 배운 개념이고, 재귀로 구현하면 더 간단한 하고 간편한 경우도 있으니, 재귀로도 구현할 수 있도록 잘 정리해두고 가자.
재귀의 대명사: 팩토리얼!
다음은 재귀의 기본구조로 풀 수 있는 문제라고 알려진 팩토리얼이다.
- 재귀 풀이
def factorial(n):
if n==0:
return 1
else:
return n*factorial(n-1)
print(factorial(a))- dp 풀이
import sys
input = sys.stdin.readline
n= int(input())
dp = [0]*13
dp[0]=1
dp[1]= 1
dp[2]= 2
for i in range(3,13):
dp[i]=i*dp[i-1]
print(dp[n])depth가 있는 재귀
def func(n, depth):
print('시작', depth)
if n == 0:
print('탈출!', depth)
return
else:
print('들어가는 중~', depth)
func(n-1, depth+1)
print('종료되는 중!' , depth)
func(3,0)
##결과
시작 0
들어가는 중~ 0
시작 1
들어가는 중~ 1
시작 2
들어가는 중~ 2
시작 3
탈출! 3
종료되는 중! 2
종료되는 중! 1
종료되는 중! 0앞으로 깊이를 조절하면서 재귀함수를 호출하기 위해 다음과 같은 구조의 재귀함수를 쓸 일 이 많을 것이다.
'시작'이 써있는 구문에는 함수가 호출되면 무조건 실행되며,
'들어가는 중~'으로 써있는 구문은 재귀호출하는 곳의 앞부분으로 더 깊은 곳의 함수를 호출할 때 실행되는 곳이다.
'탈출!'구문은 원하는 깊이까지 도달했을 때 실행되는 코드,
'종료되는 중!'은 호출이 종료되고 나오면서 실행되는 코드다.
하노이탑
https://www.acmicpc.net/problem/1914
https://youtu.be/FYCGV6F1NuY
다시푸는 건데도 풀이가 바로 떠오르지않았다. 재귀의 정의처럼 문제를 쪼개고 반복함으로써 풀 수 있는 재귀의 대표적인 문제다.
m은 원반의 개수
a는 시작 기둥
b는 목표 기둥
c는 보조 기둥
가장 큰 원반을 목표 기둥에 옮기려면 보조기둥이 그 전(m-1)의 원반들이 모두 옮겨져 있어야 한다. -> hanoi(m-1, a, c, b)
목표 기둥에 옮긴다는 건 출력으로만 보여주고 있기때문에 print(a, b)으로 보여준다.
시작,보조 기둥을 바꾸는 것을 통해 목표기둥에 원반을 쌓는다.
n = int(input())
def hanoi(m, a, b, c):
if m>20:
return
if m == 1:
print(a,b)
return
# 목표에 제일 큰 원반을 넣기 위해서는 그 전에 보조기둥에 나머지 원반을 끼어넣어야한다!
hanoi(m-1, a, c, b)
print(a, b) # 가장 큰 원반을 목표 기둥에 옮기는 코드
hanoi(m-1, c,b, a) # 시작,보조 기둥을 바꾼다.
print(2**n-1)
hanoi(n,1,3,2)N-Queen
https://www.acmicpc.net/problem/9663
https://youtu.be/gcuZ_VGIcn4
대표적인 재귀함수, 백트래킹 문제다.
퀸이 위치할 수 있는 모든 경우의 수를 찾으라는 문제이기때문에 백트래킹으로 풀 수 있다.
n이 1,2,3...인 경우를 보면 어느정도 반복, 중복되는 규칙이 보인다.
또한 decision space를 줄이기 위해서 한줄에는 1개의 퀸만 놓을 수 있다고 생각하자!
import sys
input = sys.stdin.readline
n = int(input()) # 체스판 크기
# 각 열에 퀸이 어느 행에 위치하는지 저장하는 리스트
cols = [0] * n
# 대각선 상에 퀸이 존재하는지 확인하는 리스트
# 좌상단 -> 우하단 대각선: row - col + n - 1
# 우상단 -> 좌하단 대각선: row + col
diagonal1 = [False] * (2*n - 1) # 좌상단 -> 우하단 대각선
diagonal2 = [False] * (2*n - 1) # 우상단 -> 좌하단 대각선
count = 0 # 가능한 경우의 수 카운트
# 재귀 함수
def n_queen(row):
global count
# 모든 열에 퀸이 놓였다면, 경우의 수 카운트
if row == n:
count += 1
return
for col in range(n):
if not (cols[col] or diagonal1[row-col+n-1] or diagonal2[row+col]):
cols[col] = diagonal1[row-col+n -
1] = diagonal2[row+col] = True # 해당 위치에 퀸 놓기
n_queen(row+1) # 다음 행으로 이동
cols[col] = diagonal1[row-col+n -
1] = diagonal2[row+col] = False # 퀸 놓은 위치 초기화
n_queen(0) # 첫 번째 행부터 시작
print(count)z문제
재귀는 문제를 더 작은 하위 문제로 분할하고, 각 하위 문제의 결과를 결합하여 원래 문제를 해결하는 방식이다.
분할 정복 알고리즘.
제일 작은 경우를 정의해 보자.
"""
import sys
input = sys.stdin.readline
N, r, c = map(int, input().split())
def sol(N, r, c):
if N == 0:
return 0
return 2*(r % 2)+(c % 2) + 4*sol(N-1, int(r/2), int(c/2))
print(sol(N, r, c))