재귀함수

 

재귀함수란

 

 유사한 하위 작업 형태로 정의할 수 있는 작업을 처리하는 데 유용하게 쓰인다.

예를 들어 정렬이나 검색, 종주 문제에는 간단한 재귀적인 형태의 풀이가 있는 경우가 흔하다.

 

재귀적인 루틴에서는

자기 자신을 호출하여 하위 작업을 처라하는 방식(=재귀 케이스)으로 작업의 일부분을 수행한다.

 

재귀 호출을 하다보면 자신을 호출하지 않고도 처리할 수 있는 하위 작업(=기본 케이스)이 나온다.

 

이렇게 루틴에서 자기 자신을 호출하는 것을 재귀 케이스라 말하고,

자기 자신을 호출하지 않아도 되는 경우를 기본 케이스라고 부른다.

 

재귀 알고리즘에는 재귀 케이스와 기본 케이스, 이렇게 두 가지 케이스가 있다.

 

간단하고 널리 알려저 있는 예제인 팩토리얼 연산을 통해 이 개념을 확인해보자.

 

// n이 1초과일 경우의 팩토리얼 논리 로직

n!(n 팩토리얼이라고 읽음)은 1부터 n까지의 모든 정수를 곱한 값이다.

예를 들어 4! = 4 x 3 x 2 x 1 이다.

n!을 더 형식적으로 정의하면 다음과 같다.

 

// n이 1보다 작거나 같을 때의 팩토리얼 논리 로직 

n! = n x (n-1)!;

0! = 1! = 1

 

이 정의로부터 팩토리얼을 재귀적으로 구현하는 방법을 바로 유추할 수 있다.

작업은 n! 값을 구하는 것이며, 하위 작업은 (n-1)! 값을 구하는 것이다.

 

재귀적인 케이스는 n이 1보다 큰 경우로,

자기 자식을 호출하여 (n-1)! 값을 구한 다음 거기에 n을 곱한다.

 

위의 논리를 살펴보면

n이 0 또는 1인 기본 케이스에서는 그냥 1을 반환하면 된다.

 

만약 해당 로직을 구현할 때

반드시 n 값이 1씩 줄어들 때마다 기본 케이스에 이르도록 만들지 못한다면,

재귀 호출은 무한이 반복될 것이다.

 

하지만 실제로는 무한히 반복되진 않는다.

언젠가는 스택 오버플로우가 발생하면서 프로그램이 멈춰버리는 사고가 발생하기 때문이다.

즉 모든 재귀 케이스는 결국에는 기본 케이스로 넘어가야만 한다.

 

재귀 호출에서 반환한 값 자체가 곧바로 반환되면 그 함수는 꼬리 재귀 호출 함수라고 한다.

해당 로직은 꼬리 재귀 호출 함수로 구현하지 않았지만,

 

꼬리 재귀 호출의 경우에는

일부 컴파일러에서는 꼬리 재귀 호출 함수에 대해 꼬리 호출 제거 작업을 처리하여

각 재귀 호출에 대해서 같은 스택 프레임을 재사용하는 최적화를 적용한다.

잘 최적화된 꼬리 재귀 호출 함수는 스택 오버플로우 없이 무한히 재귀 호출될 수 있다.

 

재귀호출 팁

 

다시 팩토리얼 구현법으로 돌아오자면,

팩토리얼 구현법은 가장 간단한 재귀 호출 루틴의 한 예시이다.

많은 경우에 재귀 호출 레벨을 추적하기 위한 인자 또는 추가 자료구조가 필요하다.

 

그런 경우에는 될 수 있으면

그러한 자료구조 또는 인자를 초기화하는 코드를 별도의 루틴에 집어넣는 것이 좋다.

 

초기화 작업을 수행한 다음에 순수하게 재귀적인 루틴을 호출하는 래퍼 루틴을 이용하면

프로그램의 나머지 부분에 대해 깔끔하고 단순한 인터페이스를 제공할 수있다.

 

레퍼란 뜻은 한 번 감싸서 동작한다는 뜻이다.

 

즉 레퍼 루틴이라는 것은 한 번 감싸주는 루틴 즉,

레퍼 함수를 응용하자는 말이 된다.

즉 레퍼 함수는 기존함수를 한 번 감싸서 원래 동작에 약간의 처리를 추가해 주는 함수라는 것이다.

별 거 없다 뭔가를 감싸주는 것이다.

 

대부분 초기화에 필요한 과정을 담아두는 함수이다.

 

vector<int> allFactorials(int n) {
	/* 래퍼 함수 */

	vector<int> results(n == 0 ? 1 : n);
	doAllFactorials(n, results, 0);

	return results;
}

 

이렇게 레퍼 함수를 사용하면

배열 할당 및 재귀 호출 레벨 추적을 모두 숨길 수 있기 때문에 재귀 호출을 깔끔하게 만들 수 있다.

 

복잡한 재귀 호출의 함수의 경우에는 초기화를 위한 래퍼 함수를 별도로 포함하는 것이 좋다.

 

재귀호출의 특징

 

하지만 재귀 호출이 매우 강력한 테크닉이긴 하지만,

언제나 가장 좋은 접근법이라고는 할 수없다.

일반적으로 재귀호출 가장 효율적인 접근법인 경우가 거의 없기 때문이다.

 

팩토리얼 연산처럼 단순한 재귀 호출의 루틴의 경우에는 

상당수의 컴퓨터 아키텍처에서 실제 계산보다는 호출에 따르는 오버헤드 때문에

더 많은 시간을 소모하게 된다. ( => 많은 비용 발생, 가장 효율적인 접근법 x)

 

재귀적인 호출 대신

반복문을 사용하는 반복적인 루틴의 경우 이런 오버헤드가 필요 없기 때문에

일반적으로 효율이 더 좋다.

 

즉 반복적인 풀이법이 재귀적인 풀이법에 비해 일반적으로 더 효율적이다.

또한 재귀적으로 풀 수 있는 문제는 어떤 문제든 반복적인 풀이법으로도 풀 수 있다.

 

작업 자체가 재귀적인 특성을 가지고 있다고 하더라도

비교적 쉽게 반복적인 알고리즘으로 만들 수 있다.

 

int factorial(int n)
{
	int val = 1;
	for (int i = n; i > 1; i--)
	{
		/* n=0 또는 1일 때는 그냥 넘어감 */
		val *= i;
	}

	return val;
}

 

 

이런 구현을 사용하면 루틴 호출을 하지 않아도 되기 때문에

앞에서 만들었던 재귀적인 구현에 비해 훨씬 더 효율이 좋아진다.

문제에 대해 생각하는 법 자체가 달라지긴 했지만,

재귀적인 구현법에 비해 구현하기가 더 난이도가 높지는 않다.

 

문제에 따라 위에 나온 것처럼 반복적인 구현법이 쉽게 떠오르지 않는 것도 있다.

하지만 언제든 재귀 호출을 사용하지 않고 재귀적인 알고리즘을 구현하는 것이 가능하다.

 

재귀 호출은 일반적으로 지역 변수의 현재 값을 보존해다가

재귀 호출에 의해서 수행되는 하위 작업이 완료되었을 때 다시 가져와서 쓰기 위해서 쓰인다.

 

지역 변수는 프로그램의 스택에 할당하기 때문에

루틴이 재귀적으로 호출될 때마다 별도의 지역 변수를 가지게 되며,

이런 이유 때문에 재귀 호출을 하게 되면 자동적으로 프로그램의 스택에 변수의 값이 저장된다.

 

따라서 직접 스택을 만들고 수동으로 지역 변수 값을 그 스택에 넣고 꺼내면 재귀 호출을 쓰지 않아도 된다.

 

	vector<int> results(n == 0 ? 1 : n);
	doAllFactorials(n, results, 0);

 

 

이렇게 스택을 기반으로 하는 반복형 루틴을 만드는 방법은

같은 루틴을 재귀 호출을 써서 구현하는 것에 비해 훨씬 복잡하다.

 

게다가 스택을 쓰는 데 드는 오버헤드가

함수 호출에 필요한 오버헤드보다 훨씬 적은 게 아닌 이상

이렇게 만든 함수가 일반 재귀 호출로 만든 함수보다 많이 빠르지도 않다.

따라서 별 다른 얘기가 없다면 재귀적인 알고리즘은 재귀 호출을 써서 구현하는 게 낫다.

재귀 호출을 쓰지 않고 알고리즘을 오버헤드를 생각해가며 구현하는 것도 좋다.

 

 

중요도

1. 제대로 작동하는 풀이

2. 효율적인 풀이

 

면접에서 별도의 지시 사항이 없으면

가장 먼저 떠오르는 제대로 작동하는 풀이 방법을 사용하는 것이 좋다.

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <list>
#include <stack>
#include <algorithm>

using namespace std;


int doAllFactorials(int n, vector<int> &results, int level)
{
	if (n > 1) {
		/* 재귀 케이스 */
		results[level] = n * doAllFactorials(n - 1, results, level + 1);
		return results[level];
	}

	else
	{
		/* 기본 케이스 */
		results[level - 1] = 1;
		return 1;
	}
}

vector<int> allFactorials(int n) {
	/* 래퍼 함수 */

	vector<int> results(n == 0 ? 1 : n);
	doAllFactorials(n, results, 0);

	return results;
}

int factorial(int n)
{
	int val = 1;
	for (int i = n; i > 1; i--)
	{
		/* n=0 또는 1일 때는 그냥 넘어감 */
		val *= i;
	}

	return val;
}




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n = 5;

	vector<int> results = allFactorials(n);
	for (int i = 0; i < results.size(); i++)
		cout << results[i] << " ";

	cout << factorial(n);

	return 0;
}