재귀함수의 기본적 이해
재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수입니다.
예제 코드로 확인해보면
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void Recursive(int num)
{
if (num <= 0) return;
printf("Recursive Call! %d \n", num);
Recursive(num-1);
}
int main(void)
{
Recursive(3);
return 0;
}실행 과정은
시작 (n = 3)
void Recursive( 3 )
{
if (3 <= 0) return; // false 이므로 리턴 X
printf("Recursive Call! %d \n", 3);
Recursive(3-1); // num값이 2로 바뀌며 재귀 호출
}num = 2
void Recursive( 2 )
{
if (2 <= 0) return; // false 이므로 리턴 X
printf("Recursive Call! %d \n", 2);
Recursive(2-1); // num값이 1로 바뀌며 재귀 호출
}num = 1
void Recursive( 1 )
{
if (1 <= 0) return; // false 이므로 리턴 X
printf("Recursive Call! %d \n", 1);
Recursive(1-1); // num값이 0로 바뀌며 재귀 호출
}num = 0
void Recursive( 0 )
{
if (0 <= 0) return; // true 이므로 종료
printf("Recursive Call! %d \n", 0);
Recursive(0-1);
}재귀의 탈출 조건을 구성하는 것은 매우 중요한데 탈출 조건이 잘못될 경우 무한 반복이 되기 때문이다.
재귀함수의 디자인 사례
재귀함수로 재귀적인 수학적 수식을 그대로 옮길 수 있는데
디자인 사례로 Factorial 값을 반환하는 함수를 재귀적으로 구성해보자
먼저 n!의 수식적 의미는
위 수식은 밑처럼 표현할 수 있는데
이를 n팩토리얼 f(n)은 수식적으로
f(n) = n x f(n-1) ... n >= 1
1 ... n = 0이렇게 표현할 수 있다.
여기서 이므로 이것이 재귀함수의 탈출조건이 된다.
팩토리엉 값을 반환하는 함수의 이름을 Factorial이라고 하고
n이 1이상인 경우 은
if(n >= 1)
return n * Factorial(n-1);n = 0인 경우 결과값 1은
if(n == 0)
return 1;위 두 코드를 묶어보면
if(n == 0)
return 1;
else
return n * Factorial(n-1);이런 팩토리얼 함수를 완성할 수 있다.
확인해보기 위해 입력 값을 팩토리얼로 나타내는 전체 코드로 확인해보면
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int Factorial(int n)
{
if(n == 0)
return 1;
else
return n * Factorial(n-1);
}
int main(void)
{
int n;
scanf("%d", &n);
printf("%d 팩토리얼은 : %d\n", n, Factorial(n));
return 0;
}실행 결과를 보면 Factorial 함수의 logic이 잘못되지 않았음을 확인할 수 있다.
재귀의 활용
피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열인데
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
이런 식으로 앞의 두 수를 더해서 현재의 수를 만들어가는 수열이다.
수식으로 나타내보면
fib(n) = 0 ... n = 1
1 ... n = 2
fib(n-1) + fib(n-2) ... n >= 3 그럼 이를 재귀함수로 표현해보면
int Fibo(int n)
{
if(n == 1) return 0;
else if (n == 2) return 1;
else return Fibo(n-1) + Fibo(n-2);
}이렇게 될 것이다. 코드를 확장하여 제대로 정의되어있는 것인지 확인해보자
#include <stdio.h>
int Fibo(int n)
{
if(n == 1) return 0;
else if (n == 2) return 1;
else return Fibo(n-1) + Fibo(n-2);
}
int main (void)
{
for (int i = 1; i < 15; i++)
{
printf("%d ", Fibo(i));
}
return 0;
}실행결과
0 1 1 2 3 5 8 13 21 34 55 89 144 233 이진 탐색 알고리즘의 재귀적 구현
이진 탐색 알고리즘 자체는 재귀적인 성질을 가지고 있는데
1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
2. 저장되어있지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작
그리고 탐색의 실패가 결정되는 시점은
"탐색 범위의 시작위치를 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우"
위 조건들을 가지고 함수를 만들어보면
int BSearchRecur(int ar[], int first, int last, int target)
{
...
}ar[] : 탐색할 array
first : 탐색 범위의 시작위치
last : 탐색 범위의 끝
target : 찾으려는 값
먼저 탐색의 실패를 코드로 나타내보면
int BSearchRecur(int ar[], int first, int last, int target)
{
if (first > last)
return -1;
}-1 반환은 탐색의 실패를 의미한다.
그리고 탐색 범위의 중앙을 나타내는 변수 mid를 설정한다.
int BSearchRecur(int ar[], int first, int last, int target)
{
int mid;
mid = (first + last) / 2;
if (first > last)
return -1; // 탐색에 실패한 경우
if(ar[mid] == target)
return mid; // mid값이 목표값인 경우 mid를 반환
else if (ar[mid] > target)
return BSearchRecur(ar, first, mid-1, target);
else return BSearchRecur(ar, mid+1, last, target);
}이진 탐색 알고리즘을 재귀함수 기반으로 구현하면 성능이 떨어지지만 재귀함수에 익숙해지는데 그 목적이 있다.
하노이 탑 문제
하노이 탑 문제는 재귀적 사고의 대표적인 예시로, 주어진 원반을 한 기둥에서 다른 기둥으로 이동시키는 문제이다. 문제 해결의 핵심은 n-1개의 원반을 중간 기둥으로 옮긴 후, 가장 큰 원반을 최종 기둥에 옮기고, 다시 n-1개의 원반을 최종 기둥으로 이동시키는 것이다.
구현 예시
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void Hanoi(int n, char from, char by, char to) {
if (n == 1)
printf("원반1을 %c에서 %c로 이동\n", from, to);
else {
Hanoi(n - 1, from, to, by);
printf("원반%d을 %c에서 %c로 이동\n", n, from, to);
Hanoi(n - 1, by, from, to);
}
}
int main(void) {
Hanoi(3, 'A', 'B', 'C'); // 예시로 원반 3개
return 0;
}실행 결과
원반1을 A에서 C로 이동
원반2을 A에서 B로 이동
원반1을 C에서 B로 이동
원반3을 A에서 C로 이동
원반1을 B에서 A로 이동
원반2을 B에서 C로 이동
원반1을 A에서 C로 이동문제 해결 로직
-
n-1개의 원반을 중간 기둥으로 이동.
-
가장 큰 원반을 최종 기둥으로 이동.
-
중간 기둥의 n-1개의 원반을 최종 기둥으로 이동.
이러한 방식으로 n개의 원반을 옮기는 과정을 반복하는 재귀적 해결이 필요하다.
https://www.acmicpc.net/problem/11729
위 문제로 바로 적용해보자
