[자료구조] 순환

순환(Recursion)

어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

 

가장 대표적인 예시로 정수의 팩토리얼을 구현한 함수가 있다

int factorial(int n) 
{
	if(n<=1) return 1;
	else return n*factorial(n-1);
}

이 구조에서는 매개 변수로 n이 들어오게 되면 다시 n과 (n-1)!의 곱으로 바뀌게 된다

이런식으로 반복하여 매개변수가 1이 될때까지 순환을 이어나갈 것이다

그리고 마침내 매개변수의 값이 1이 되었을 때, 순환을 통해 나온 결과 값(n부터 1까지의 곱)을 반환하고 빠져나간다

 

내부 구현

프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다

복귀 주소가 시스템 스택에 저장되고, 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다

이런 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record)라 한다

모든 준비가 끝나면 호출된 함수 코드의 시작 위치로 점프하여 수행을 시작하는데,

순환 함수는 자기 자신의 시작 위치로 점프하여 수행하고,

수행이 끝나면 시스템 스택에서 복귀 주소로 호출하여 호출한 함수로 돌아간다

시스템 스택의 변화

 

활성화 레코드

- 활성화 레코드는 스택에 저장되는 것으로서 "스택 프레임(Stack Frame)"이라고도 한다

- 운영체제가 메인 함수를 호출하는 순간  메인 함수의 활성화 레코드가 생성된다

- 활성화 레코드는 반환값, 값 파라미터, 반환 주소, 지역 변수 네 가지로 분류된다

1. 반환 값(Return Value) : 피 호출 함수가 호출 함수에게 반환하는 값

2. 값 파라미터(Value Parameter) : 호출 함수가 피 호출함수에게 넘기고자 하는 값

3. 반환 주소(Return Address) : 함수가 호출된 곳의 다음 주소(보통 해당 번지수+명령문 길이-단위:byte)

4. 지역 변수(Local Variables) : 함수 내에서 선언된 지역 변수를 저장하는 곳

 

순환의 원리

※ 순환은 단순하게 문제를 전혀 해결하지 않고 순환 호출을 하는 것이 아니고, 대부분 일부 문제를 해결한 다음 순환 호출을 한다

주어진 문제를 더 작은 동일한 문제들로 분할하여 해결하는 방법을 분할정복이라 한다

순환 호출을 하게 되면 분할정복 방법에 따라서 문제의 크기는 점점 작아지게 되고, 해결하기 쉬워진다

 

순환 알고리즘의 단점

순환 알고리즘을 사용하면 가독성이 높아지는 좋은 장점이 있지만, 모든 경우에 적용하기 좋은 방법은 아니다

대표적으로 위의 피보나치 예시를 통해 반복 알고리즘과 순환 알고리즘을 비교해 보면

for 문을 이용한 반복 알고리즘도 n번 반복하고, 순환 알고리즘도 매 순환시 곱셈을 하기 때문에

두 방법 모두 시간 복잡도가 O(n)이 된다

하지만 순환 호출의 경우, 함수를 호출하기 위해 스택을 사용하고 이전 함수의 상태를 저장한 여분 공간이 필요하기 때문에

반복 알고리즘보다 여분 공간이 더 필요하고 시간이 더 오래 걸리게 된다