[자료구조] 재귀(Recursion)

재귀(Recursion)란?

함수가 자기 자신을 호출하여 문제를 해결하는 기법이다.

 

일반적으로 재귀 함수는 두 가지 구성 요소를 가진다.

• 기본 조건(Base Case): 재귀 호출을 종료시키는 조건
• 재귀 조건(Recursive Case): 함수가 자기 자신을 호출하는 조건

---

특징

• 문제를 작은 단위로 나누어 해결한다.
• 함수 호출 과정에서 스택 메모리를 사용한다.
• 무한 재귀 호출이 발생하면 스택 오버플로우(Stack Overflow)가 발생할 수 있다.

---

장단점

• 장점
  - 코드가 간결하여 가독성이 높다.
  - 트리나 그래프 탐색과 같은 계층적 문제 해결에 적합하다.
• 단점
  - 반복적으로 호출되므로 성능이 떨어질 수 있다.
  - 스택 메모리를 과도하게 사용할 경우 문제가 발생한다.

---

재귀 함수의 구조

void recursiveFunction(매개변수) {
	if (기본 조건) {
    	// 기본 조건에 도달하면 종료
        return;
    } else {
    	// 재귀 조건
        recursiveFunction(변경된 매개변수);
    }
}

---

예제

1. 팩토리얼(Factorial)

• 정의: n! = n x (n - 1)!
• 기본 조건: 0! = 1

int factorial(int n) {
	if (n == 0) { // 기본 조건
    	return 1;
    } else { // 재귀 조건
    	return n * factorial(n - 1);
    }
}

 

2. 피보나치 수열(Fibonacci Sequence)

• 정의: F(n) = F(n - 1) + F(n - 2)
• 기본 조건: F(0) = 0, F(1) = 1

int fibonacci(int n) {
	if (n == 0) {
    	return 0;
    } else if (n == 1) {
    	return 1;
    } else {
    	return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

---

시간 복잡도

• 팩토리얼: O(n)
• 피보나치 수열: O(2ⁿ) (중복 계산 발생)
  => 해결 방법: 메모이제이션(Memoization) 또는 동적 프로그래밍(Dynamic Programming)을 사용하여 최적화

---

반복문과 재귀 비교

구분	재귀	반복문
코드 간결성	간결하고 직관적	코드가 길어질 수 있음
성능	스택 메모리 사용으로 비효율적	반복문 사용으로 효율적
적용성	트리, 그래프 등 계층적 문제	단순 반복 작업에 적합
디버깅 난이도	호출 스택 추적 어려움	비교적 쉽다

 

---

Tail Recursion(꼬리 재귀)

Tail Recursion은 재귀 호출이 함수의 마지막 작업인 경우를 말한다.

컴파일러가 이를 반복문으로 최적화하여 스택 메모리 사용을 최소화할 수 있다.

예제

int tailFactorial(int n, int result) {
	if (n == 0 ) {
    	return result;
    }
    return tailFactorial(n - 1, n * result);
}