재귀(Recursion)

1. 재귀 함수란 무엇인가?

재귀함수란 한마디로 정의하자면 함수 내에서 자신을 호출하는 것을 의미한다. 자신을 호출하게 된다면 함수를 재진입하는 것이 아니라 자신과 동일한 함수를 복사한다. 종료 조건이 없다면 무한 루프에 빠지기 때문에 종료 조건이 반드시 필요하다. 종료 조건을 만나게 된다면 단계적으로 처음 호출한 함수로 돌아오게 된다.

2. 재귀 함수의 디자인 사례

재귀함수는 자료구조나 알고리즘의 문제를 단순화 하는데 중요하게 사용된다. 재귀는 수학적 수식을 그대로 코드로 옮길 수도 있는데 팩토리얼(factorial)값을 예로 들수 있다. 팩토리얼은 n!로 n! = n * (n-1) * (n-2) * ... * 2 * 1 로 나타낼 수 있다. 이 패턴을 재귀함수를 이용해 디자인하게 될수있다.

#include <stdio.h>

int Factorial(int n) {
	if(n == 0)
	  return 1;
	else
	// 자기 자신을 복제하여 호출한다.
	  return n * Factorial(n - 1);
}

int main(void) {
	printf("1! = %d\n", Factorial(1));
	printf("2! = %d\n", Factorial(2));
	printf("3! = %d\n", Factorial(3));

	return 0;
}

>> 1! = 1
>> 2! = 2
>> 3! = 6

이 과정은 재귀함수를 구현하는데 있어서 중요한 모델이 되기 때문에 코드를 이해하는게 아니라 흐름을 이해하여야한다.

3. 이진 탐색 알고리즘의 재귀적 구현

이진 탐색은 리스트의 중간 지점부터 시작하여 탐색 대상을 찾을 때까지 동일한 패턴을 반복한다. 이런 성격은 재귀적은 성질이다. 때문에 재귀적으로 정의가 가능하다.

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target){
	int mid;
    
    if(first > last)
    	return -1
	// 탐색 대상의 중간을 찾는다.
    mid = (first + last) / 2;
	if(ar[mid] == target)
		return mid;
	else if(ar[mid] > target)
		return BSearchRecur(ar, first, mid-1, target);
	else
		return BSearchRecur(ar, mid+1, last, target); 	
}

int main(void) {
	int idx;
	int arr[] = {1, 3, 5, 7, 9};

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 7);
	if(idx == -1)
		printf("탐색실패\n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1, 4);
	if(idx == -1)
		printf("탐색실패\n");
	else
		printf("타겟 저장 인덱스 : %d\n", idx);
        
	return 0;
}

 

4. 하노이 타워

하노이 타워에 대해 자세히 설명이 되어 있는 블로그를 링크한다. 하노이 타워를 재귀함수 기반으로 해결하게 된다면 원반의 수와 상관없이 동작이 가능하다. 재귀의 특징은 코드의 양이 줄어든다는 것이다. 하노이 타워의 문제를 해결하기 위해 작성한 코드의 양을 보면 이해가 가능하다.

https://splendidlolli.tistory.com/344