순환과 재귀(Recursion)

이재원·6일 전

알고리즘 재귀

알고리즘

목록 보기

22/23

순환

재귀적 알고리즘에서 순환은 재귀 호출의 반복적 구조를 의미하며, 이는 문제가 작은 부분 문제로 계속 나뉘고, 그 결과를 결합하여 최종 결과를 도출하는 과정이다.

순환의 예

순환은 본질적으로 순환적인 문제가 그러한 자료구조를 다루는 프로그램에 적합하다. 예를 들어 정수의 팩토리얼은 다음과 같이 정의된다.

$n! = \begin{cases} 1 & \text{if } n = 0 \\ n \cdot (n-1)! & \text{if } n \geq 1 \end{cases}$

즉 위의 정의에서 팩토리얼 n!을 정의하는데 다시 팩토리얼 (n-1)!이 사용되었다. 이러한 정의를 순환적이라 한다. 위의 정의에 따라 n!을 구하는 함수 factorial(n)을 구현하면 다음과 같다.

int factorial(int n) {
	printf("factorial(%d)\n", n);
	if(n <= 1) return 1;
	else return (n * factorial(n-1));
}

이 함수는 아래와 같은 과정을 통해 알고리즘이 수행된다.

따라서 위 출력문의 결과는 다음과 같다.

factorial(3)
factorial(2)
factorial(1)

순환 호출의 내부적인 구현

스택 영역의 역할

스택 영역은 프로그램 실행 중에 함수 호출과 복귀를 관리하는 메모리 영역이다.
함수를 호출하면 해당 함수의 매개변수(parameter), 지역 변수, 복귀 주소 등을 담은 공간이 스택에 저장된다.
이렇게 저장된 함수의 정보를 담은 공간을 활성 레코드(Activation Record)라고 부른다.

활성 레코드(Activation Record)

활성 레코드는 특정 함수 호출에 필요한 모든 정보를 포함하는 스택의 단위이다.

주요 구성 요소

복귀 주소: 함수 호출이 끝난 후 돌아갈 위치를 저장한다.
매개 변수: 호출된 함수에 전달된 인자 값이다.
지역 변수: 함수 내부에서 선언된 변수들이 저장된다.
임시 결과: 계산 중간값이나 필요한 임시 저장 공간이다.

순환 호출에서의 스택 동작

재귀(순환 호출)가 일어나면 함수가 계속 호출되면서 새로운 활성 레코드가 스택에 쌓인다.
각 호출의 활성 레코드는 독립적이므로, 매개변수와 지역 변수가 서로 겹치지 않는다.
예를 들어, factorial(n) 함수가 factorial(n-1)을 호출 할 때 일어나는 과정은 아래와 같다.

1. factorial(n)의 활성 레코드가 스택에 저장된다.
2. factorial(n-1)이 호출되면, 새로운 활성 레코드가 스택에 추가된다.
3. 이러한 과정이 재귀적으로 반복되면서 스택이 깊어지게 된다.

만약 재귀 호출이 무한히 반복되어 스택이 계속 쌓이면, 메모리 오버플로우(Stack Overflow)가 발생할 수 있다. 따라서 적절한 탈출 조건을 명시해 줘야 한다.

함수 종료와 스택 복구

호출된 함수의 실행이 끝나면, 스택에서 해당 활성 레코드를 제거한다.
스택의 가장 위에 있는 활성 레코드가 제거되면, 복귀 주소에 따라 이전 함수로 돌아가 실행을 이어간다.
재귀 호출의 종료 조건이 총족되면 스택에 쌓인 활성 레코드들이 순차적으로 제거되면서 프로그램이 종료된다.

순환을 지원하지 않는 언어

C, pascal, C++, Java 등의 현대적인 프로그래밍 언어에서는 순환을 지원하기에 재귀 호출이 가능하지만, portran, cobol과 같은 고전적인 언어에서는 지역변수가 없거나 있더라도 정적으로 할당되므로 순환이 불가능하다.

즉, 함수호출마다 새로운 지역변수를 만들지 못하면 이전 호출과 구분할 수 없어 순환 호출이 불가능하다.

Head Recursion(머리 순환) vs Tail Recursion(꼬리 순환)

Head Recursion

재귀 호출이 함수 내부에서 가장 먼저 실행되는 형태의 재귀이다. 재귀 호출이 끝난 뒤에 나머지 연산이 수행된다.

실행 순서

재귀 호출이 먼저 실행된다
가장 깊은 단계까지 재귀 호출이 진행된 후, 스택이 차례대로 반환하면서 나머지 연산이 수행된다.

특징

재귀 호출이 먼저 실행되므로 스택 프레임이 계속 쌓인다.
함수가 종료될 때까지 아무런 작업이 완료되지 않아, 스택 메모리 사용량이 많아질 수 있다.
일반적으로 대부분의 재귀 함수는 머리 순환(Head Recursion)이다.

예시

맨 처음에 다뤘던 팩토리얼 함수

int factorial(int n) {
	printf("factorial(%d)\n", n);
	if(n <= 1) return 1;
	else return (n * factorial(n-1));
}

Tail Recursion

재귀 호출이 함수 내부에서 가장 마지막에 실행되는 재귀이다.

재귀 호출 뒤에 더 이상 다른 연산이 없으므로, 현재 함수의 작업이 끝난 상태에서 재귀 호출이 실행된다.

특징

함수의 모든 연산이 재귀 호출 이전에 완료된다
재귀 호출이 마지막에 위치하므로 현재 활성 레코드를 더 이상 유지할 필요가 없다.
컴파일러가 이를 감지하면 스택 프레임을 재사용하게 된다.
→ 새로운 프레임을 쌓는 대신 기존 프레임을 덮어씌우는 방식으로 최적화
→ 이것이 Tail Call Optimization(TCO)이다.

int factorial(int n, int result) {
	printf("factorial(%d)\n", n);
	if(n == 1) return 1;
	return factorial(n-1, n * result);
}

/*
factorial(5, 1) → 
factorial(4, 5) → 
factorial(3, 20) → 
factorial(2, 60) → 
factorial(1, 120)
*/

스택 프레임 재사용 이유

재귀 호출 이후에 추가 작업이 없으므로 컴파일러는 현재 함수의 스택 프레임을 그대로 재사용 할 수 있다.

결과적으로 새로운 활성 레코드가 추가되지 않고, 메모리 사용량이 줄어든다.

이러한 점 때문에 꼬리 재귀는 반복문처럼 최적화될 수 있다.

순환 ↔ 반복

순환(재귀)

장점

본질적으로 순환적인 문제나 자료구조에 적합
알고리즘을 명확하고 간결하게 표현할 수 있다.

단점

수행 속도가 반복에 비해 떨어질 수 있다(오버헤드 발생할 수 있음)
스택 메모리를 사용하기 때문에 메모리 사용량이 증가할 수 있다.

반복

for나 while 같은 반복 구조를 사용하여 특정 작업을 반복 실행하는 방식이다.

장점

구현이 간단하고 효율적으로 동작할 수 있다.
반복 알고리즘은 일반적으로 수행 속도가 빠르다.

단점

복잡한 문제에서는 반복을 사용하면 코드가 지나치게 복잡해질 수 있다.

반복적인 팩토리얼 프로그램

int factorial_iter(int n) {
	int i, result = 1;
	for(i = 1; i <= n; i++)
		result = result * i;
	return result;
}

반복 알고리즘과 순환 알고리즘의 성능

for문을 사용하여 n번 반복하므로 시간 복잡도는 $O(n)$ 이다.
순환 호출은 n번 일어나므로 역시 $O(n)$ 이다. 하지만 순환의 경우 호출할 때마다 활성 레코드를 스택에 할당하고 회수해야 하기 때문에 메모리를 더 많이 사용하고, 오버헤드가 발생할 수 있다.
결론적으로 순환 알고리즘은 이해하기 쉽고, 프로그래밍 하기 쉽다는 장점이 있는 대신 수행 시간과 기억 공간의 사용에 있어서는 비효율적인 경우가 많다.

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구

이재원

20학번 새내기^^(였음..)

이전 포스트

2-3트리

다음 포스트