[자료구조] 2. 재귀 (Recursion)

윤성우 저자님의 "윤성우의 열혈 자료구조" 책을 학습하고 정리한 글입니다.

 

1. 함수의 재귀적 호출의 이해

📌 재귀 함수 (Recursion)

함수 내에서 자기 자신을 다시 호출하는 함수

• 재귀 함수를 실행하는 중간에 다시 재귀 함수를 호출하면, 재귀 함수의 복사본을 하나 더 만들어서 실행하게 된다.
• 하지만 '재귀의 탈출조건'이 없다면 무한히 복제하기 때문에 '재귀의 탈출조건'을 정의해야 한다.

2. 재귀의 활용

2-1. 팩토리얼 함수 (Factorial)

// RecursiveFactorial.c

#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);
		printf("4! = %d \n", Factorial(4);
		printf("9! = %d \n", Factorial(9);
		return 0;
}

/*
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880
*/

 

2-2. 피보나치 수열

// FibonacciFunc.c

#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)
{
		int i;
		for(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
*/

 

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

// RecursiveBinarySearch.c

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)
{
		int mid;
		if(first > last)
				return -1;            // -1의 반환은 탐색의 실패를 의미
		mid (first+last) / 2;     // 탐색대상의 중앙을 찾는다.
		
		if(ar[mid] == target)
				return mid;           // 탐색된 타겟의 인덱스 값 반환
		else if(target < ar[mid])
				return BSearchRecur(ar, first, mid-1, target);
		else
				return BSearchRecur(ar, mid+1, last, target);
}

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

/*
타겟 저장 인덱스: 3
탐색 실패
*/

 

 

참고자료

책 - 윤성우의 열혈 자료구조 (2012년 1월)