[SW사관학교정글] WEEK01 개발일지 - Ⅱ

재귀함수

재귀함수란

재귀함수는 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다. 즉, 함수 정의 내에 같은 이름의함수가 올 때 이를 재귀함수라 한다. 재귀함수 사용 시 반드시 탈출 조건이 있어야 stack overflow를 방지할 수 있다.

재귀함수의 기본 구조

int sum(int n) 
{
	# 탈출 조건
	if (1 == n) {
		return 1;
	
	# 자신보다 1만큼 작은 숫자를 분신을 만들어서 계산을 시킨다.
	# 분신이 계산을 마치면 자신의 현재 값을 거기에 더한다.
	} else {
		return sum(n-1) + n;
	}
}

재귀함수의 호출 및 리턴 과정

모든 함수는 호출되면 메모리에 새로운 공간을 확보해서 매번 전혀 다른 공간에서 작업이 진행된다. 소스 코드에서는 같은 공간처럼 보이지만 실제 실행되는 코드는 전혀 다른 공간에서 이뤄진다

main() 함수에서 처음 재귀함수를 실행했을 때 "재귀함수 1"이라는 메모리 공간이 생겨서 작업을 진행하다가 다시 재귀함수를 실행한다면 새로 "재귀함수 2"이라는 메모리 공간이 생성되는 방식이다.

이런 방식을 반복하다보면 같은 코드가 메모리 공간만 옮겨다니면서 무한히 반복되기 때문에 메모리가 부족할 때까지 멈추지 않고 반복하다가 프로그램이 종료되는데, 이것 때문에 재귀함수를 작성할 때에는 언제 멈춰야 할지 탈출조건이 필요하다.

위의 그림에서 "재귀함수 3"은 탈출조건을 만나서 실행이 멈추게되고 이후 이전 함수로 복귀하여 나머지 코드를 진행하고 다시 이전 함수로 복귀하는 과정이 계속 진행된다.

TIP
함수의 실행코드는 메모리에 한 번만 저장되어 같은 공간인 것이 맞지만, 로컬 변수 및 파라메터 등은 전혀 다른 공간에서 새로 생성되어 이전 함수 호출과 전혀 연관없는 진행이 이루어진다. 따라서 호출 할 때마다 새로운 객체가 생성된다고 생각하면 된다.

재귀함수의 장단점

재귀함수의 장점

• 이해하기 쉽다.
• 쉽게 프로그램 할 수 있다.
• 변수 사용을 줄여준다.

재귀함수의 단점

• 시간복잡도가 반복문에 비해 계산이 어렵다.
• 반복문보다 큰 오버헤드를 가진다 ( 반복문보다 메모리 사용량 많고 수행 시간이 더 길어질 수 있다 )
• 함수 호출을 많이 하기에 StackOverFlow 가능성이 있다.
• 종결조건이 A 측면, B 측면에서도 확실해야 한다. 그렇지 않으면 무한 반복이 일어난다.
• 무한반복이 일어나는 경우 CPU 크래쉬를 초래한다. ( 반복문의 경우 메모리가 부족할 때가 되면 알아서 멈춤 )

재귀 함수 관련 백문 문제 Github 링크
백준 재귀함수 관련 문제