재귀

---

1. 재귀란

1-1. 개론

재귀함수는 함수 내에서 자신을 다시 호출하는 함수를 말한다. 아주 간단한 예시를 들어보자면 다음과 같다.

void recursion() {
    recursion();
}

1-2. 재귀의 흐름

팩토리얼의 정의를 살펴보자

$N!$
$= N \times (N-1) \times \cdot\cdot\cdot \times 1$
$= N \times (N-1)!$

팩토리얼을 N과 (N-1)의 팩토리얼의 곱으로 나타낼 수 있음을 알 수 있다. 점화식으로 나타내면 다음과 같다.

$N \in \mathbb N$일 때
1. $fac(1) = 1$
2. $fac(N) = N \times fac(N-1)$

위의 식을 통해 팩토리얼이 재귀적으로 정의됨을 알 수 있다. 흐름을 나타내보면 다음과 같다.

이처럼 재귀 구조는 어떤 문제를 해결하기 위해 그보다 조금 더 작은 문제를 해결하고, 그 결과를 이용해 원래 문제를 해결한다. 이때 '조금 더 작은 문제'를 '부분 문제'라고 부른다.

1-3. 재귀의 구현

재귀 함수의 필수 요소로 다음 두가지가 있다.

1. 재귀 호출
2. 종료 조건

1은 너무 당연한 내용이니 넘어가자. 종료 조건(base case)은 재귀 함수가 재귀 호출을 중지하고 현재 함수를 종료(return)하는 조건을 말한다. 위의 팩토리얼 예시에서 $fac(0)$이 종료 조건이다. 만약 위 예시에서 종료 조건이 없다면 $fac(3) = 3 \times 2 \times 1 \times 0 \times -1 \times \cdot\cdot\cdot$ 처럼 무한히 뻗어나갈 것이다. 따라서 더이상 쪼갤 수 없는, 가장 작은 부분 문제의 답을 미리 정의함으로써 종료 조건을 지정해야 한다.

---

2. 코드 샘플

📢 코드 샘플은 이 곳에서 공개 중입니다.

2-1. Fibonacci

👀 소개

피보나치 수열은 다음과 같이 정이된다.

피보나치 수열의 a번째 요소를 fib(a)으로 표현하면
1. $fib(0) = 0$
2. $fib(1) = 1$
3. $fib(N) = fib(N-1) + fib(N-2)$

피보나치 수열이 재귀적으로 이뤄져 있음을 알 수 있다. 그림으로 나타내보면 다음과 같다.

$fib(3)$은 $fib(2)$와 $fib(1)$을 구한 뒤 그 합으로 구한다. $fib(2)$는 $fib(1)$과 $fib(0)$의 합으로 구할 수 있다. 식으로 풀어보면 다음과 같다.

$fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + fib(1)$

따라서 미리 정의한 $fib(0)$과 $fib(1)$를 이용해 $fib(3)$을 구할 수 있다.

📜 소스코드 (C++)

• $fibo(N)$은 $N$번째 피보나치 수를 반환한다.
• line 4, 8 : $N$이 0 또는 1일 때 각각 0과 1을 반환한다.
• line 12 : $N$이 2 이상일 때 $fibo(N-1) + fibo(N-2)$를 반환한다. (피보나치 수열의 정의 활용)

✨ 결과

입력

10

출력

55

• $N$번째 피보나치 수를 출력한다.

---