재귀 호출(Recursion)

재귀란?

- 수학이나 컴퓨터 과학 등에서 자신을 정의할 때, 자기 자신을 재참조하는 방법

- 재귀 함수의 형태로 많이 사용

 

재귀 호출의 개요

1. 재귀 호출이란?

1) 정의

"자기 자신을 호출하여 순환 수행되는 것"

▪ 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식 보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음

 

2) 특성

대표적인 분할 정복 알고리즘

 ① 문제의 크기 N

 ② 큰 문제를 작은 문제로 환원

 ③ 작은 문제 역시 큰 문제와 유사함

 ④ Self Call, Boomerang

 

2. 재귀 호출의 예

1) 팩토리얼(Factorial) 연산

 ▪ 1~n의 모든 자연수를 곱하여 구하는 연산

 ▪ 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복

 ▪ Factorial 함수에서 n=4인 경우의 실행

재귀 호출의 활용(1)

1. 이진 탐색

BinarySearch(SearchRange) // → 괄호 안은 탐색 범위
{ 
	if (One Page) // → 베이스 케이스
		Scan Until Found; 
	else 
	{ 
    	Unfold the Middle Page; // → 가운데 펼침
		Determine Which Half; // → 전반부, 후반부 판단
		if First Half
			BinarySearch(First Half); // → 전반부 재귀 호출
		else 
        	BinarySearch(Second Half); // → 후반부 재귀 호출
	} 
}

 ▪ 문제 크기 감소: N, N/2, N/4, …., 1

 ▪ 재귀 호출은 반드시 베이스 케이스(위 코드에서 if (one Page)…)에 도달해야 함

 

2. 팩토리얼 연산

 ▪ n! = n•(n-1)•(n-2)•...•1(단, 1! = 0! = 1)

int Factorial(int n) 
{ 
	if (n = = 1)
		return 1; 
	else 
		return(n * Factorial(n-1)); 
}

1) 재귀 호출을 이용한 Factorial 프로그램 실행 화면

3. 활성화 레코드

int Factorial(int n) 
{ 
	if (n = = 1)
		return 1; 
	else 
		return(n * Factorial(n-1)); 
}

재귀 호출의 활용(2)

1. 문자열 뒤집기

1) 예시1

void Reverse(char S[ ], int Size) // → 호출 함수로 되돌아 감
{ 
	if (Size = = 0) 
		return;
	else 
	{ 
    	printf("%c", S[Size-1]); // → 마지막 문자를 쓰기
		Reverse(S, Size-1); // → 재귀 호출
	} 
}

 ▪ 마지막 문자를 먼저 제거하는 방식

 

2) 예시2 - 문자열 ‘PET’에 대해 추적해 보기

void Reverse(char S[ ], int First, int Last)
{ 
    if (First > Last) 
		return;
	else 
    { 
    	printf("%c", S[First]);
		Reverse(S, First+1, Last); 
	} 
}

2. 피보나치 수열

1) 정의

 ▪ Fn = Fn-1 + Fn-2 , Where the first two terms are 1

   다른 형태로는 F(n) = F(n-1) + F(n-2)

 ▪ Each term is the sum of the previous two terms

 ▪ Sequence: { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … }

 

2) 자연에서의 피보나치 수열

3) 예시

 ▪ F(n) = F(n-1) + F(n-2) ※ 단, F(0) = 0, F(1) = 1

int Fibonacci(int n) 
{ 
	if (n < 2) // → 베이스 케이스
		return 1; // → F(0) = F(1) = 1
	else 
    	return (Fibonacci(n-1) + Fibonacci(n-2)); // → 재귀 호출
}

4) 피보나치 수열의 재귀 호출