• 6 min read

cpp[9] - 재귀함수

알고리즘을 위한 C++

원하는 기능을 함수라는 단위로 묶어서 소스코드를 간편하게 처리하는 법에 대해서 배워보았습니다.

이 기능을 구현함에 있어서 자기 자신이 필요하다면 어떻게 될까요?
이를 "재귀함수" 를 통해 해결할 수 있습니다.

재귀함수란?

재귀(recursion) 이란 다시 돌아오다 라는 의미를 가지고 있습니다.

EZ2ON BGA] Chaotic Neutral - aran - YouTube
aran - Chaotic Neutral [from EZ2ON Reboot : R]

딱 이런 이미지로 이해해주시면 됩니다.
여기서 "돌아온다" 라는 것은, 함수의 시작점으로 돌아오다 라는 맥락으로 이해해주시면 됩니다.

바로 예시 문제를 통해서 보도록 하겠습니다.

10872번: 팩토리얼
Baekjoon Online Judge스타트링크 (Startlink)

boj 10872 팩토리얼입니다.
반복문을 사용하여 해결하는 풀이가 가장 잘 알려져 있지만, 굳이 재귀함수를 통해서 한번 해결을 해보겠습니다.

먼저, 반복문을 사용한 풀이는 아래와 같습니다.

#include <iostream>
using namespace std;

int main(){
	int N,M=1;
	cin >> N;
	for(int i=1; i<=N; i++) M*=i;
	cout << M;
}

for문이 반복하면서 $N!$ 을 구하게 됩니다.
여기서 주된 의미인 팩토리얼을 구하자 를 분리하겠습니다.

#include <iostream>
using namespace std;

int fac(int K){
	int ret=1;
	for(int i=1; i<K; i++) ret*=i;
	return ret;
}

int main(){
	int N;
	cin >> N;
	cout << fac(N);
}

팩토리얼을 여러번 구해야 할때는 다음과 같은 함수를 작성하는게 보다 깔끔한 프로그램을 작성할 수 있습니다.

저 fac 함수를 더 깔끔하게 만들수는 없을까요?
여기서 재귀함수가 등장합니다.

재귀함수와 팩토리얼

팩토리얼의 정의를 보겠습니다

$$ N! = N*(N-1)(N-2) \cdots 32*1 $$

팩토리얼은 다음과 같이 정의되는데,
이 정의를 그대로 차용하면 $(N-1)!$ 은 아래와 같습니다.

$$ (N-1)! = (N-1)(N-2)(N-3) \cdots 321 $$

이때, 위 식의 양변에 N을 곱하면

$$ N*(N-1)! = N*(N-1)(N-2) \cdots 32*1 $$

이라는 식을 얻으며,
여기서 우변은 $N!$ 이 됨에 따라 $N*(N-1)! = N!$ 이 성립합니다.
이걸 이용해서 재귀함수를 작성해보면

#include <iostream>
using namespace std;

int fac(int K){
	if(K==1 || K==0) return 1;
	return K * fac(K-1);
}

int main(){
	int N;
	cin >> N;
	cout << N;
}

반복문 없이 팩토리얼을 계산할 수 있습니다.
이때, fac(N) 을 계산하기 위해서는 먼저 fac(N-1)이 먼저 계산되야 하는것에 주의해주세요.

이렇듯 자기 자신을 계산하기 위해 자기 자신을 또 불러 계산 시키는 것이 재귀함수에 해당합니다.

재귀함수와 무한반복

재귀함수는 자기 자신을 부르게 된다는 특징상, 종료 조건을 반드시 지정해주어야 합니다. 종료 조건이 없는 재귀함수는 while(true) 와 같이 무한 반복하게 된다는것을 항상 주의하며 작성해야 합니다.

위의 소스코드에서는

if(K==1 || K==0) return 1;

구문이 종료 조건을 담당하는 부분입니다.
K가 1씩 작아지면서 호출되어지다가 마지막에 1이나 0이 되면 반환,
다시 fac(2) -> fac(3) -> fac(4) 순으로 반환되며
처음 호출했을 때의 역순으로 값을 계산해 올라갑니다.

재귀함수와 while

재귀함수는 조건에 맞을때 종료한다는 점에서,
조건에 맞지 않을때 종료하는 while문과 굉장히 비슷한 특징을 지닙니다.

10952번: A+B - 5
Baekjoon Online Judge스타트링크 (Startlink)

boj 10952 A+B - 5 문제입니다.
while문을 통한 문제 풀이가 잘 알려져 있지만, 재귀함수로 작성할 시 보다 깔끔합니다.

#include <bits/stdc++.h>
using namespace std;

void aplusb(){
	int a,b;
	cin >> a >> b;
	if(a==0 && b==0) return;
	cout << a+b;
	aplusb();
}

int main(){
	aplusb();
	return 0;
}

탈출 조건 a==0 && b==0 에 걸리지 않은 경우, 두 수의 합을 출력하고
재귀함수를 통해 같은 실행을 반복합니다.

실행 횟수가 명확하게 정해진 반복의 경우에는 재귀함수를 사용하는 것보다 for문을 사용한 반복문이 보다 직관적이지만,
이러한 문제와 같이 실행 횟수가 쉽게 바뀔 수 있거나 예측할 수 없는 경우
재귀함수를 사용하는 것이 보다 깔끔하게 구현할 수 있는 경우가 있습니다.

결론

재귀함수는 그 특성상 실행횟수가 불명확한 보다 복잡한 형태의 알고리즘 작성에 자주 쓰이게 됩니다.

대표적인 사용으로는 DP, 동적 프로그래밍 알고리즘 기법에 관하여 학습할 때에 위에서부터 아래로 내려가는 "메모이제이션" 기법은 대부분 재귀함수로 구현이 됩니다.

함수와 마찬가지로 프로그램의 가독성을 위한 선택사항 중의 하나이기에, 재귀함수를 강제하는 문제는 그렇게 많지 않은 편입니다.

while문을 사용하는것이 적합하다고 생각하는 문제를 해결하실 때, 재귀함수도 고려 선상에 올려두시고 문제를 해결하시면 도움이 될 것입니다.

추천 글

featured