재귀(Recursion)

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

자기 자신을 순환적으로 호출하는 부분 그리고 순환 호출을 멈추는 부분으로 구성되어 있다.

 

이해를 돕기 위해 재귀 알고리즘의 기본적 예시인 팩토리얼과 거듭제곱 계산 문제로 살펴보겠다.

 

 

 순환(재귀 함수 활용)

#include <iostream>

using namespace std;

int factorial(int num) {
	cout<<"factorial"<<"("<<num<<")"<<endl;
	if(num <= 1) return 1;
	else return num * factorial(num - 1);
}

int main() {
	int n, result;
	cin>>n;
	result = factorial(n);

	cout<<result<<endl;
}

 

변수 n을 입력받아 재귀적으로 함수를 호출하여, n에 대한 팩토리얼의 값을 출력하는 코드이며,

시스템 스택에서 순환호출하는 과정은 다음과 같다.

 

순환호출 과정

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

factorial(num-1) {
	if(num-1<=1) return 1;
	else return (num-1 * factorial(num - 2))
}

factorial(num-2) {
	if(num-2<=1) return 1;
	else return (num-2 * factorial(num - 3))
}

~
~

factorial(1) {
	if(1<=1) return 1; // 순환 호출 종료.
	~ 
}

------------------------------------------------------------------------------------------
factorial(num) = num * factorial(num-1)

              =	 num * factorial(num-1) * factorial(num-2)

              =	 num * factorial(num-1) * factorial(num-2) * ~~ * factorial(1)	

              =	 num * factorial(num-1) * factorial(num-2) * ~~ * 1

              =	 num * factorial(num-1) * num-2 * ~~ * 1		

              =	 num * num-1 * num-2 * ~~ * 1

 

 

num이 매개변수로 들어와 순환 호출이 종료되는 부분인 1이 될때까지 반복해서 호출하게 된다. 스택 프레임이 하나씩 할당되며 호출이 끝나면 후입선출의 구조로 1부터 차례대로 반환되면서 팩토리얼의 값을 얻을 수 있다.

 

순환 알고리즘은 반복 알고리즘으로도 구현할 수 있는데 차이를 보기 위해서 다음의 코드를 확인해보자.

 

 반복

#include <iostream>

using namespace std;


int main() {
	int n, fact_result = 1;
	cin>>n;
	
	for(int i = 1; i<=n; i++) {
		fact_result *= i;
	}
	cout<<fact_result<<endl;
}

 

함수화되어 있는 부분만 비교해봤을 때 순환 알고리즘의 경우 가독성의 측면과 소스 코드를 쉽게 짤 수 있다는 장점이 있지만, 반복 알고리즘에 비해 수행 시간과 기억 공간의 사용에 있어서 비효율적이다.

 

시간복잡도는 O(n)으로 같으나, 함수를 호출하고 스택에 저장하는것과 같은 부가적인 작업이 있어서 수행 시간이 더 걸리며 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야 하므로 기억 장소가 상대적으로 더 많이 필요하다.

 

 

 

 

다음은 순환과, 반복을 이용해 거듭제곱을 계산했을 때의 시간복잡도를 비교해보겠다.

 

반복을 이용한 거듭제곱 계산

#include <iostream>

using namespace std;

int main() { 
	int x, n, result = 1;
	cin>>x>>n;
	
	for(int i = 0; i<n; i++) {
		result*=x;
	}
	
	cout<<result<<endl;
}

 

반복문을 활용하여 거듭제곱을 계산했을 때, 밑이 x인 수를 n 제곱한 것에 대한 시간복잡도는 O(n)이 나오는 것을 확인할 수 있다.

 

재귀를 활용한 거듭제곱 계산

#include <iostream>

using namespace std;

int power(int x, int n) {
	if(n==0) return 1;
	else if(n%2==0) return power(x*x, n/2);
	else return x*power(x*x, (n-1)/2);
}

int main() { 
	int x, n, result;
	cin>>x>>n;
	
	result = power(x, n);
	
	cout<<result<<endl;
}

 

반복문과 달리 순환은 호출을 할 때마다 문제의 크기가 약 절반으로 줄어들기 때문에 O(log n)의 시간복잡도를 가지면서 팩토리얼 예제와 달리 수행시간이 순환을 활용했을 때가 더 빠르다.

 

반복문으로 구현한 코드는 루프 당 곱셉 한 번이므로 n만큼 반복하고, 재귀적으로 구현한 코드는 호출 시 연산의 개수가 곱셈뿐만 아니라, 나눗셈도 일어나므로 log n에 비례한다.

 

이와 같이 재귀 알고리즘은 장단점이 문제 상황에 따라 존재하기 때문에 반복, 재귀로 구현했을 때 코드 간결성 및 효율성을 비교해보고 문제를 해결하는 것이 순환 문제를 풀 때 이상적인 접근 방식이라 할 수 있다.