2. 재귀(Recursion)

1. 재귀함수의 기본적인 이해 

 

 

재귀 함수 호출 원리

 

샘플

 

void RecursionFunction(int icnt)
{
	if (icnt < 0)  return;

	cout << "재귀 호출: " << icnt << endl;
	
	RecursionFunction(icnt -1);
}




int main()
{
    RecursionFunction(11);

    return 0;
}

 

실행화면

 

---

재귀함수의 디자인 사례

▶ 팩토리얼(factorial)

 

수학적 표현

 

//코드
if(n==0) return 1;
else
    return n* Factorial(n-1);

 

샘플

 

int FactorialFunc(int inum)
{
	if (inum == 0)
	{
		return 1;
	}
	else
	{
		return inum * FactorialFunc(inum - 1);
	}
}

int main()
{
	cout << FactorialFunc(1) <<endl;
	cout << FactorialFunc(3) << endl;
	cout << FactorialFunc(4) << endl;
	cout << FactorialFunc(5) << endl;
	cout << FactorialFunc(6) << endl;
	cout << FactorialFunc(7) << endl;

	return 0;
}

 

실행화면

 

---

2. 재귀의 활용

 

▶ 피보나치 수열

 

 

 

//코드

int Fibofunc(int inum)
{
	if (inum==1) 
		return 0;
	
	else if(inum ==2)	
		return 1;
	
	else	
		return Fibofunc(inum - 1) + Fibofunc(inum - 2);
}

 

예제

 

int Fibofunc(int inum)
{
	if (inum == 1)	
		return 0;		
	else if (inum == 2)	
		return 1;	
	else	
		return Fibofunc(inum - 1) + Fibofunc(inum - 2);	
}


int main()
{
	for (int i = 1; i < 15; i++)
	{
		cout << Fibofunc(i) << ", ";
	}
	return 0;
}

 

실행화면

 

▶ 피보나치 수열 함수의 흐름

 • 재귀 함수의 호출 순서를 정리하는 것은 큰 의미가 없음.

 • 따라서 재귀함수 자체를 정확히 이해하고 사용하 는 것이 중요함

• 위 그림은 이진 트리 구조가 보임

• 이진 탐색으로도 사용 할수 있을거 같다.

---

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

1. 탐색종료 설정
2. 탐색 목표설정
3. 계속 탐색 설정

 

 

1장에서 했던 이진탐색 함수와 재귀기능이 합쳐 졌다.

int BSearct(int arr[], int len, int target)
{
	int first = 0;
	int last = len - 1;
	int mid;

	while (first <= last)
	{
		mid = (first + last) / 2;
		if (target == arr[mid])
		{
			return mid;
		} 
		else
		{
			if (target < arr[mid]) //  
			{
				last = mid - 1;
			}
			else // target > arr[mid]
			{
				first = mid + 1;
			}
		}
	}
	return -1;
}

void RecursionFunction(int icnt)
{
	if (icnt < 0)  return;

	cout << "재귀 호출: " << icnt << endl;
	
	RecursionFunction(icnt -1);
}

▼

int BSearchRecur(int arr[], int first, int last, int target)
{
	int mid;

	if (first > last)
		return -1;

	mid = (first + last) / 2;

	if (target == arr[mid])
	{
		return mid;
	}
	else
	{
		if (target < arr[mid])
		{
			return BSearchRecur(arr, first, mid - 1, target); //작으면 앞 탐색
		}
		else
		{
			return BSearchRecur(arr, mid+1, last, target); /크기 뒤 탐색
		}
	}
}

---

3. 하노이 타워

 

▶ 하노이 타워 문제의 이해

 

▶ 하노이 타워 해결의 예

 

 

▶ 반복되는 일련의 과정을 찾기 위한 힌트

 

▶ 하노이 타워의 반복패턴 연구

 

 

목적. n개  A->C

1. 작은 원반 n-1개 A->B

2. 큰 원반1개 A->C

3. 작은 원반 n-1개 B->C

 

 

▶ 하노이 타워 문제의 해결