재귀 함수와 반복문의 비교(recursion function)

1. 재귀 함수란?

한자로 풀어서 해석하면 다시 "재(再)" 돌아올 "귀(歸)", 말 그대로 다시 돌아오다 라는 뜻이다.

프로그래밍의 관점에서 재귀란 "함수 자신을 다시 호출하다"라는 의미이다.

 

2. 재귀함수의 쓰임

재귀함수는 기본적으로  현재의 condition을 유지한 상태로 전의 작업과 비슷한 행동을 할 때 매우 유용한 알고리즘이다. 이러한 재귀함수의 특성때문에 stack, 분할정복 등의 많은 문제에서 활용되곤 한다. 

 

다음은 재귀함수로 간단하게 구현할 수 있는 문제이다.

https://wondrous-developer.tistory.com/1

[백준 17609] 회문 (C++)

 

---

 

이외에도 재귀함수는 여러가지 알고리즘, 자료구조 등을 구현할 때 유용하게 쓰인다.

반복문

재귀함수는 함수 자신을 다시 호출함으로써 같은 일을 반복한다는 점에서 반복문과 매우 비슷하게 쓰인다. 따라서 모든 재귀 함수는 반복문으로 다시 작성할 수 있다.

 

---

자료구조 (stack, tree, ...)

stack은 FIFO(First In First Out)의 자료구조를 가진다. 함수도 마찬가지로 FIFO의 자료구조를 가진다. 왜냐하면 메모리에서 함수가 호출되고 종료될 때에도 블록 단위(C언어에서는  중괄호{ } 단위, 파이썬에서는 들여쓰기 단위)로 제일 마지막에 호출된 함수가 제일 먼저 메모리상에서 종료되기 때문이다.

[호출]: 첫 번째 func() 호출 → 두 번째 func() 호출 → 세 번째 func() 호출
[종료]: 첫 번째 func() 종료 ← 두 번째 func() 종료 ← 세 번째 func() 종료

따라서 stack을 사용해야 하는 여러 문제에서 유용하게 활용된다. 대표적으로 스택을 이용한 괄호쌍 문제나 트리구조를 구성할 때 재귀함수를 사용한다.

 

---

 

분할 정복 알고리즘

분할 정복은 복잡한 문제를 여러 부분으로 나누어서 단순하게 해결해준다는 점에서 많이 쓰이는 알고리즘이다.

L트로미토 알고리즘, 하노이탑, 피보나치 수열 등이 대표적인 예이다.

재귀 함수도 같은 행위를 반복한다는 점에서 분할 정복 알고리즘에서 많이 활용된다.

 

다음은 분할정복 알고리즘을 활용는 유명하고 널리 알려진 대표적인 예시이다.

https://wondrous-developer.tistory.com/9

분할 정복 대표 예시: 하노이탑(hanoi top)

https://wondrous-developer.tistory.com/7

분할정복 대표예시: L-트로미노 타일링(L-tromino)

 

---

탐색 알고리즘

탐색 알고리즘 중에서도 DFS(깊이 우선 탐색)이나 백트래킹, 트리의 순회 등에서도 재귀함수가 쓰인다. 다음은 백트래킹을 이용해 풀 수 있는 간단한 조합문제이다.

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

 

 

3. 재귀 함수와 반복문의 비교

재귀함수만이 가지는 특징

그렇다면 재귀함수는 반복문에 비해 어떤 특징을 가질까?

 

모든 반복문은 재귀함수로 짤 수 있지만 모든 재귀함수는 반복문으로 짤 수 없다. 즉 재귀함수가 반복문보다 더 복잡하고 까다로운 구현이 가능하다.

 

바로 위의 문제 [백준15650번] N과 M (2)를보자.

N = 5, M = 3인 경우 C(5, 3)을 출력해보면 다음과 같이 반복문, 재귀함수 두 가지로 코드를 짤 수 있다.

//반복문으로 구현한 조합
#include<iostream>
using namespace std;

int main(void) {
	//ex) C(5, 3)
	for (int i = 1; i <= 5; i++) {;
		for (int j = i+1; j <= 5; j++) {
			for (int k = j+1; k <= 5; k++) {
				cout << i << " " << j << " " << k << "\n";
			}
		}
	}
	return 0;
}

//재귀함수로 구현한 조합 풀이
#include <iostream>
using namespace std;
int N, M;
int seq[100];
void backtracking(int cur, int num){
    //base condition
    if(cur == M) {
        for(int i=0; i<M; i++) cout << seq[i] << " ";
        cout << "\n";
        return;
    }
    for(int k=num; k<=N; k++){
        seq[cur] = k;
        backtracking(cur+1, k+1);
    }
}
int main()
{
    
    cin >> N >> M;
    backtracking(0, 1);
    
    return 0;
}

 

반복문의 경우에는 반복문의1부터 5까지 돌며 반복문을 3번 사용하면 된다. 하지만 N과 M이 미리 정해지지 않은 변수라면 반복문이 M번 필요하다. 이렇게 원하는 만큼(M번) 반복시키는 경우에는 재귀함수로만 가능하다.

 

정리하자면 재귀함수가 반복문보다 더 복잡하고 까다로운 구현이 가능하다.

그러나 재귀 함수가 장점만 있는 것은 아니다. 위에서 언급했듯이 함수가 한 번 호출될 때마다 stack의 메모리 공간을 차지한다. 일부 컴파일 환경에서는 1MB정도의 메모리 제한이 걸려있다. 따라서 재귀함수를 10만번 정도 호출하면 stack overflow가 발생하는 경우가 많다. 그만큼 함수가 점유하는 메모리의 공간이 크다는 것이다. 다른 지역변수들과 함께 사용할 경우 그만큼 함수가 차지할 수 있는 메모리의 공간은 적어지게 된다.

 

재귀함수 최적화

물론 꼬리재귀라는 재귀함수를 최적화할 수 있는 방법이 있지만 이는 해당 언어가 꼬리재귀최적화를 지원해야 가능하므로 제한적이다.(참고로 C++과 java는 이를 지원한다.) 궁금한 사람들은 아래링크를 참고하길 바란다.

https://velog.io/@dldhk97/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98%EC%99%80-%EA%BC%AC%EB%A6%AC-%EC%9E%AC%EA%B7%80

재귀함수와 꼬리 재귀

 

따라서 stack을 초과할 것 같으면 반복문으로 구현하거나 동적 계획법(Dynamaic Programming)과 함께 사용해야 한다. (아니, 거의 필수적으로 Dynamic Programming과 함께 사용해야 한다고 볼 수 있다!)

---

정리

이를 정리하면 다음과 같다.

재귀함수의 장점

• 코드의 가독성이 좋아진다.
• 반복문으로는 할 수 없는 복잡하고 까다로운 구현이 가능하다.
• 코드의 길이를 획기적으로 줄일 수 있다.

재귀함수의 단점

• stack영역의 메모리를 많이 차지한다.
• 그냥 사용할 경우 시간복잡도가 너무 커질 수 있다.

사용자마자 호불호가 갈리지만 어떻게 사용하는가에 따라 장점이 많아질 수도 있는 만큼 장점을 살려서 잘만 사용하면 이만한게 없는 기법이다.

 

참고로 재귀함수를 수준급으로 마스터하면 수준높은 복잡한 구현도 가능하다.