재귀함수란?
재귀함수는 함수 내부에서 자기 자신을 호출하는 함수를 일컫는다.
#include <stdio.h> void recursive() { printf("재귀함수 호출\n"); recursive(); } int main() { recursive(); return 0; }
예제 1.1
재귀함수 호출 재귀함수 호출 재귀함수 호출 재귀함수 호출 재귀함수 호출 ...
출력 1.1
재귀함수는 자기 자신을 호출하기 때문에 무한히 반복될 수 있다. 그렇다면 무한 루프에 빠지지 않기 위해서는 어떻게 해야 할까?
종료 조건
재귀함수가 무한 루프에 빠지지 않기 위해 종료 조건을 설정할 수 있다. 종료 조건이 참이면 더이상 함수를 호출하지 않고 return을 통해 함수를 종료할 수 있다.
#include <stdio.h> void recursive(int n) { if (n == 0) { return; } printf("재귀함수 호출\n"); recursive(n - 1); } int main() { recursive(3); return 0; }
예제 1.2
재귀함수 호출 재귀함수 호출 재귀함수 호출
출력 1.2
피보나치 수열
피보나치 수열은 다음과 같은 수열을 일컫는다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
피보나치 수열은 다음과 같은 점화식으로 표현할 수 있다.
f(n) = f(n - 1) + f(n - 2)
피보나치 수열을 재귀함수로 구현해보자.
#include <stdio.h> int fibonacci(int n) { if (n == 1 || n == 2) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n; scanf("%d", &n); printf("%d\n", fibonacci(n)); }
예제 1.3
10
입력 1.3
55
출력 1.3
팩토리얼
팩토리얼은 다음과 같은 연산자이다.
n! = n * (n - 1) * (n - 2) * ... * 1
이는 다음과 같은 점화식으로 표현할 수 있다.
n! = n * (n - 1)!
따라서, 팩토리얼을 재귀함수로 구현해보자.
#include <stdio.h> int factorial(int n) { if (n == 1) { return 1; } return n * factorial(n - 1); } int main() { int n; scanf("%d", &n); printf("%d\n", factorial(n)); }
예제 1.4
10
입력 1.4
3628800
출력 1.4
재귀함수를 이용한 문제 풀이 팁
부분 문제 정의
부분 문제란 큰 문제를 작은 문제로 나누어 해결하는 것을 말한다. 재귀 함수는 이러한 부분 문제를 해결하고 이를 결합하여 최종적으로 큰 문제를 해결하는 데에 유용하게 사용된다.
예를 들어, 이전에 풀었던 피보나치 수열 문제의 경우 10번째 수를 구하기 위해 이를 9번째 수를 구하는 부분 문제와 8번째 수를 구하는 부분 문제로 나누었다. 또한, 이 부분 문제들을 더 작은 하위 부분 문제로 나누는 과정을 반복하고 이를 결합하여 최종적으로 10번째 수를 구하는 문제를 해결할 수 있었다.
기저 조건
기저 조건이란 부분 문제를 더 이상 나눌 수 없을 때 재귀 함수를 더이상 호출하지 않고 종료할 수 있는 조건을 말한다.
예를 들어, 피보나치 수열의 1번째 수와 2번째 수는 1이므로 이를 기저 조건으로 설정할 수 있다.
11729번: 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729
부분 문제 정의
기둥 1에서 기둥 3으로 n개의 원판을 옮기는 과정을 다음과 같은 부분 문제로 나눌 수 있다.
- 기둥 1에서 기둥 2로 n - 1개의 원판을 옮긴다.
- 기둥 1에서 기둥 3으로 남은 1개의 원판을 옮긴다.
- 기둥 2에서 기둥 3으로 n - 1개의 원판을 옮긴다.
일반화를 위해, 기둥 1을 from, 기둥 2를 by, 기둥 3을 to라고 하자. 그럼 위의 부분 문제는 다음과 같이 정의할 수 있다.
- 기둥
from에서 기둥by로 n - 1개의 원판을 옮긴다. - 기둥
from에서 기둥to로 남은 1개의 원판을 옮긴다. - 기둥
by에서 기둥to로 n - 1개의 원판을 옮긴다.
기저 조건
기둥 from에 있는 원판이 1개인 경우(즉, n = 1인 경우)에는 바로 기둥 to로 옮기면 된다.
코드
#include <stdio.h> #include <math.h> void hanoi(int n, int from, int by, int to) { if (n == 1) { printf("%d %d\n", from, to); return; } hanoi(n - 1, from, to, by); printf("%d %d\n", from, to); hanoi(n - 1, by, from, to); } int main() { int n; scanf("%d", &n); printf("%d\n", (int)pow(2, n) - 1); hanoi(n, 1, 2, 3); }