Recursive Call

재귀 호출(Recursive Call)

자기 자신을 호출하는 방식

왜 Recursive Call이 필요할까요?

미로를 탈출한다고 생각해봅시다. 막다른 길에 도달하면 이전 갈림길로 돌아가 다른 경로를 시도해야 합니다.

이처럼 여러 선택지를 모두 시도해야 할 때, 실패한 경우 이전 상태로 되돌아가는(backtracking) 과정이 필요합니다.

재귀 호출은 함수가 종료되기 전까지 상태를 유지하므로, 각 단계의 상태를(스택 구조로) 자동으로 기억합니다.

💡하나의 선택지가 끝나면 이전 상태로 돌아가 다른 선택지를 시도할 수 있습니다.

💡하나의 큰 문제를 여러 작은 문제로 분리하거나, 반복문보다 직관적이고 간결한 코드 작성이 가능합니다.

 

🔄 동작 원리

피보나치 수열을 통해 재귀 호출의 동작 원리를 살펴봅시다.

피보나치 수열

이전 두 항의 합이 다음 항이 되는 수열

• F(1) = 1
• F(2) = 1
• F(N) = F(N-1) + F(N-2) , { N ≥ 3 }

이제 피보나치 수열을 구하는 함수 F를 구현하겠습니다.

우선, N이 1 또는 2인 경우 항상 1을 반환합니다.

이는 재귀 호출이 종료되는 조건 즉 기저 사례(Base Case)라고 합니다.

def F(N):
	# Base Case
	if N == 1 or N == 2:
		return 1

이제 N ≥ 3인 경우에 대해 재귀 호출을 해야 합니다. 이를 재귀 사례(Recursive Case)라고 합니다.

 	# Recursive Case
 	else:
	  return F(N - 1) + F(N - 2)

❓F(6)을 호출하면 어떤 함수들이 호출될까요?

❓중복되는 계산이 많아요!

💡중복되는 계산은 중간 계산 값을 저장해 재활용하는 Memoization기법을 활용해 해결할 수 있습니다.

이는 Dynamic Programing에서 더 자세히 배울 수 있습니다.

 

 

연습 문제

https://www.acmicpc.net/problem/17478

 

 

재귀 깊이

Python에서는 재귀 호출의 기본 값이 1,000으로 정해져 있습니다.

sys.setrecursionlimit()를 사용해 최대 재귀 깊이를 조정할 수 있습니다.

from sys import setrecursionlimit
setrecursionlimit(1e4)

하지만, 함수의 재귀 호출이 끝나 소멸될 때 까지 함수의 지역 변수, 매개변수, 반환 주소 등의 정보가 스택 프레임 메모리에 누적 저장됩니다.

때문에, 함수의 복잡도에 따라 다르지만, 메모리 제한이 1GB인 경우 최대 재귀 깊이는 약 100,000회 정도 입니다.

💡걱정마세요! 코딩테스트에서 응시 가능한 언어라면, 이러한 부분을 고려해 문제가 출제됩니다.

만약 문제가 풀리지 않는다면 다른 방법을 사용해 해결해야 합니다!