기초 cs - 함수 9

재귀함수 (스스로 나한테 돌아오는 함수)

• 함수에서 자기 자신을 부르는 함수
• 위험한 기능
• stack overflow의 위험성 (무한호출)
• 잘쓰면 유용한
• 퍼즐게임에서 자주 쓰이는
• 코딩 테스트에서 한 문제 반드시 등장하는

void f()
{
	f(); 
	// 자신을 부르는 함수 : f를 부르면 f도착해서 부르고 부르고 무한 반복
}

Divide & Conquer (분할 정복)

• 문제를 잘라서 해결하면 쉽다
• 재귀 함수
• 문제를 잘랐더니 동일한 문제의 작은 집합인 경우에만 해당

void Print(int x)
{
	if (x < 0)
	{
		return; 
		//f(-1)이 걸리면 return; f(0)의 line 11로 들어옴 그러고 함수가 끝나면 f(1)의 line 11으로
		//f(9)인 상태에서 빠지면 그 다음에야 main()으로 돌아가게됨
	}
	
    std::cout << x << std::endl;
	Print(x - 1);
	// 9876543210
    // 먼저 출력하고 함수로 들어감
    // 먼저 출력작업하고 쌓아감
    Print(x - 1);
	std::cout << x << std::endl;
	// 0123456789
    // 먼저 재귀하고 출력
    // 다 쌓고 출력작업
	//마지막 Print(0)으로 호출되면 x=-1 -1이므로 if문에걸리면 
    //return 되고 더이상 함수를 부르지 않고 std::cout<<x 출력 
    //이때 인자는 0이므로 -1이 아니라 0에서 끝나게 됨
    
    
}

int main()
{
	Print(9);
}

---

재귀함수 부르는 패턴

void Recursive(x)
{
	if (Base Case)
	{
		return;
	}

	동일한 해법이 존재해야함
	범위는 작아저야 함
		Recursive(x-1 or x/2  등등의 x보다 작은 값의 패턴-Recursive Case);  

}

Base Case

• 더 이상 자를 수 없는 기본 상태
• 문제를 풀 수 있는 가장 작은 단위

Recursive Case

• 범위를 좁혀서 자기 자신을 호출

---

배열의 다섯개의 원소를 출력해보자

void Print(int array[5],int start, int end)
{
	
	//base case
	if (start > end)
	{
		
		return;
	
	}
	std::cout << array[start] << std::endl;
	//recursive case
	Print(array,start+1,end); // start++는 나를 증가시킴 start+1은 start에 1 추가
	//array만 쓰기 index쓰면 원소를 말하는 것
}

	//base case
	if (start<=end)
	{
		std::cout << array[start] << std::endl;
		Print(array, start + 1, end);
	}


int main()
{
	int array[5]{ 1,2,3,4,5 };

	Print(array,0,4);
}

---

배열의 합 구하기

int Sum(int array[5], int start, int end) // 원소 몇개 처리>?
{
	//base case
	if (start == end)
	{
		return array[start]	;
	}
	//recursive case

	return array[start] + Sum(array, start + 1, end);
}


int main()
{
	int array[5]{ 1,2,3,4,5 };

	Sum(array,0,4); // 배열의 합계를 구해보세요
}

---

하노이의 탑

• 만약 N-1개를 임시 공간으로 옮긴 수 있다면으로 가정해보기
• N 개 짜리는 시작지에서 도착지로 옮기는데 임시 공간을 활용하는 것으로 시작