5. STL : 재귀함수에 대해서

 

재귀함수

재귀는 대표적인 ‘분할 정복’ 알고리즘 이다.

• K번쨰 블록이 반드시 쓰러진다는 사실을 증명하시오
  • 수학적 귀납법(Mathematical Induction) - 한 조건으로 확정된 상황을 바탕으로 진행.
  • 첫번째 블록은 반드시 쓰러진다.
  • 첫번쨰 블록이 쓰러지면 두번째 블록도 반드시 쓰러진다.
  • (k-1)번째 블록이 쓰러지면 k번째 블록도 반드시 쓰러진다.
• 재귀적 알고리즘(Recursive Algorithm) - 메모리 스택을 씀.
  • 수학적 귀납법의 순서를 역순으로 증명.
• 분할 정복 :
  • 큰 문제를 작은 문제로 환원 / 작은 문제 역시 큰문제와 유사.
  • 아주 작은 문제는 반드시 해결됨( = base case)
  • 반드시 베이스 케이스에 도달해야 함.
• 팩토리얼, 문자열 뒤집기, 카운트 다운, 피보나치수열, 하노이 탑, 이진 탐색, 게임 지뢰찾기, 퍼즐

팩토리얼(n!) - 수학적으로 구조가 반복되는 것.

• 수학적 정의
  • n! = n * (n-1) * (n-2) * ….. *1(단, 1! = 0! = 1)
  1. n! = n*(n-1)!
  2. (n-1)! = (n-1) * (n-2)!
  3. ….
  4. 3! = 3 * 2!
  5. 2! = 2* 1!
  6. 1! = 1

이라고 하면 어렵지만 코드로 보면 단번에 이해 가능.

코드로 짜면?

int Factorial(int n)
{
		if(n == 1) //Base Case
			return 1; //IF 문이 없으면 스택이 계속 쌓여서 스택오버 플로우가 난다.
		else
			return (n* Factorial(n-1));
}

Value = Factorial(4) 로 인자를 4를 넣으면 위에 함수에서는 else로 들어가서 값을 리턴함.

sum(n) = n+(n-1) + … + 1

base case : n==1인 경우임.

int Sum(int n)
{
		if(n==1) 
				return 1;
		else 
				return n + Sum(n-1);//재귀호출 
}

else문에서는 Sum(n-1)은 자기 자신을 호출하므로

뭐 대충 코드로 제대로 구현을해서 알파벳 abcdefg를.. 거꾸로 바꾼다고 한다면

#include <iostream>
using namespace std;

void printReverse(char* str, int cur)
{
	//base case
	if (cur < 0)
		return;
	else
	{
		cout << str[cur];
		printReverse(str, cur - 1); 
	}
}

int main()
{
	char array[] = "abcdefg";
	int n = strlen(array) - 1;
	printReverse(array, n);
	
	return 0;
}

즉 이렇게 하면 for문 없이 재귀호출만을 이용해서 바꿀 수가 있습니다.

그럼 카운트 다운도 이제 쉽게 만들 수 있죠.

#include <iostream>
#include <Windows.h>
using namespace std;

void countDown(int n) 
{
	if (n == 0)
		return;
	else
	{
		cout << n << endl;
		Sleep(500); // 0.5초 간격으로 출력.
		countDown(n - 1);
	}
}

int main()
{
	countDown(5);

	return 0;
}

피보나치 수열

• 0, 1,1,2,3,5,8,13…
• 앞쪽에 두개를 두해서 현재 값을 계산.(0 + 1 = 1) / (1+1 = 2) …. (8 + 13 = 21)
• F(0) == 0, F(1) == 1
• 단점이라면 똑같은 놈이 계속 다른 분기에서도 중복해서 계산이 됨.
• 그래서 재귀호출을 이용해서 계산하면 효율성이 떨어짐.

그래서 재귀호출 대신 다이나믹 프로그래밍을 쓴다.

(저장 되있는 값을 불러다가 씀.)

• 하지만 우리는 지금 재귀호출을 배우니 코드는 재귀호출로…ㅎㅎ;;

int fibo(int n)
{
	if (n < 2)
		return 1;
	else
		return fibo(n - 1) + fibo(n - 2);
}

하노이탑 - 프로그래밍은 존나 어렵습니다.

• 조건
  • 한번에 한개의 디스크만 옮길수 있다.
  • 큰 디스크는 작은 디스크 위로 올라갈 수 없다.
  • 디스크는 a,b,c에만 위치 할 수 있다
  • a,b,c,를 사용가능.
• n개의 디스크를 옮기려면,
  • 디스크(n-1)개를 a에서 b로 옮긴다.
  • 디스크 1개를 a에서 c로 옮긴다.
  • 디스크 (n-1)개를 b에서 c로 옮긴다.

  if(n==1) move A To C
  ELSE
  		(n-1) move A To B
  		1번디스크 move A to C
  		(n-1) move B To C
  End IF
  

• 코드

#include <iostream>
using namespace std;

//스택구조
void HanoiTower(int n, char A, char B, char C)
{
	if (n == 1)
		cout << n << "Disk Move" << A << "to" << C;
	else
	{
		HanoiTower(n - 1, A, C, B);
		cout << n << "Move " << A << "to" << C << endl;
		HanoiTower(n - 1, B, A, C);
	}
}

int main()
{
	HanoiTower(3, 'A', 'B', 'C');

	return 0;
}

리커시브 콜(재귀호출) 사용시 함수를 반복해서

호출하므로 시간이 늘어남(안좋음)

이진 탐색

• 데이터가 정렬되어 있어야 함.
• 탐색 공간이 절반씩 줄어듦 : N, N/2, N/4 …., 1
• 데이터 (N = 10) : 1,2,5,7,8,10,15,16,17,20
• 검색 데이터 : 20

#include <iostream>
using namespace std;

int binarySearch(int num[], int low, int high, int key)
{
	int mid = (low + high) / 2;
	if (num[mid] == key)
	{
		return mid;
	}
	else if (num[mid] < key)
		binarySearch(num, mid + 1, high, key);
	else if (num[mid] > key)
		binarySearch(num, low, mid - 1, key);
}

int main()
{
	int numbers[] = { 1,2,5,7,8,10,12,15,19,20 };

	cout << binarySearch(numbers, 0, 9, 20) << endl;

	return 0;
}

//출력은 9가 나와야 함.

과제 지뢰게임에서 똑같은 숫자가 있는 곳을 클릭하면 확장될때

리커시브 콜(재귀 호출)을 이용해줘야 함.