재귀
재귀(Recursion)는 함수가 자기 자신을 호출하는 것을 말한다. 재귀의 구조는 재귀를 중단시키는 기저 조건(Base Case)과 기저 조건으로 수렴하게 되는 재귀 조건(Recursive Case)으로 구성된다.
재귀를 사용하는 이유는 문제에 따라 전체를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적*일 수 있기 때문이다. 다시 말해 복잡한 알고리즘을 단순하고 알기 쉽게 표현할 수 있다. 그뿐만 아니라 알고리즘 자체만으로는 얼마나 많은 단계를 깊이 들어가야 하는지 알 수 없을 때에도 사용할 수 있다.
*이를 분할 정복법(Divide & Conquer)이라고 한다.
예시를 살펴보자. 어떤 디렉토리가 갖고 있는 모든 파일 및 디렉토리를 지우는 함수를 구현한다고 해보자. 디렉토리에는 하위 디렉토리가 있을 수 있고, 그 하위 디렉토리에는 또 다른 하위 디렉토리가 있을 수 있으므로 같은 유형의 작업으로 분할할 수 있다.
| void RemoveAll(directory): // 재귀 조건 for childDirectory in childDirectories: RemoveAll(childDirectory) // 기저 조건 모든 파일을 지운다; |
재귀에는 한 가지 단점이 존재하는데, 함수 호출에 따른 오버헤드(Overhead)*가 있다는 것이다. 재귀가 너무 깊어지면 그만큼 호출 스택의 공간을 더 많이 사용하게 되고, 끝내는 스택 오버플로우(Stack Overflow)**가 발생할 수 있다.
*오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리 등을 말한다.
**스택 오버플로우 : 스택이 가용할 수 있는 공간을 벗어나는 것을 말한다.
구현
백준 문제와 함께 재귀를 연습해보자. 여기서는 두 문제의 풀이만 제공한다. 구현에 사용하는 코드는 C++이다.
재귀 구현할 때 꼭 등장하는 문제다. 우선은 반복문으로 팩토리얼을 구해보자.
| int fac(int n) { int result = 1; for (int i = 2; i <= n; ++i) result *= i; return result; } |
재귀와 반복문에는 상관 관계가 있어 모든 반복문은 재귀로 구현하는 것이 가능하다. 반복문을 재귀로 구현하려면 반복 변수를 매개변수에 위치시키면 된다.
| int fac(int n, int i) { // 기저 조건 : i > n보다 크면 계산이 끝난 것이다. if (i > n) // 다른 계산 식에 영향을 주지 않도록 1을 반환한다. return 1; // 재귀 조건 : result *= i; return i * fac(n, i + 1); } fac(5, 2); // 계산되는 과정은 아래와 같다. // 2 * fac(5, 3) // 2 * 3 * fac(5, 4) // 2 * 3 * 4 * fac(5, 5) // 2 * 3 * 4 * 5 * fac(5, 6) // 2 * 3 * 4 * 5 * 1 |
이를 매개변수 하나로 최적화 할 수 있는데 코드는 아래와 같다.
| int fac(int n) { if (n <= 1) return 1; // 계산이 되는 방향을 역순으로 취한다. return n * fac(n - 1); } |
보통 이렇게 역순으로 계산을 하는 것이 일반적이다.
피보나치 수 또한 재귀 문제로 가장 기초적인 문제다. 이번에는 다른 접근을 취해보려 한다. 피보나치 수의 경우 아래와 같은 점화식*을 갖게 된다.
* 점화식 : 어떤 수열의 각각의 항들의 관계를 나타낸 식이다.
어떤 문제에 대해 점화식을 세울 수 있다면 점화식을 그대로 코드로 구현하면 된다.
| int fibo(int n) { // F0 = 0, F1 = 1 if (n <= 1) return n; // Fn = Fn-1 + Fn-2 return fibo(n - 1) + fibo(n - 2); } |
백준의 나머지 문제도 풀어보자.
참고자료