[책리뷰] 윤성우의 열혈 자료구조 Ch2. 재귀

함수의 재귀적 호출의 의해

재귀함수의 기본적인 이해

void Recursive(void)
{
	cout<<"Recursive call!"<<endl;
	Recursive(); **//함수 나 자신을 재호출** 
}

• 완료되지 않은 함수를 다시 호출하는 것 가능? → 가능
• Recursive 함수가 호출되면, 원본으로부터 함수의 복사본이 만들어져서 복사본이 실행되는 구조로 이해

 

Recursive function은 한번 호출되면 계속 호출되는 문제때문에 탈출조건이 필요

재귀함수의 디자인 사례

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기

→ 재귀적인 수학 수식을 코드로 그대로 옮길 수 있음

ex) factorial

$$ f(n)= \begin{cases} n \times f(n-1), &n \ge 1 \\ 1, &n=0 \end{cases}
$$

#include <iostream>
using namespace std;

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

int main()
{
	cout << "1! = " << factorial(1) << endl;
	cout << "2! = " << factorial(2) << endl;
	cout << "3! = " << factorial(3) << endl;
	cout << "4! = " << factorial(4) << endl;
	cout << "9! = " << factorial(9) << endl;
	return 0;
}

재귀의 활용

피보나치 수열: Fibonacci Sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

#include <iostream>
using namespace std;

int fibo(int num)
{
	cout << "function call param " << num << endl;
	if (num == 1)
		return 0;
	else if (num == 2)
		return 1;
	else
		return fibo(num - 1) + fibo(num - 2);
}

int main()
{
	fibo(7);
	return 0;
}

 

function call param 7
function call param 6
function call param 5
function call param 4
function call param 3
function call param 2
function call param 1
function call param 2
function call param 3
function call param 2
function call param 1
function call param 4
function call param 3
function call param 2
function call param 1
function call param 2
function call param 5
function call param 4
function call param 3
function call param 2
function call param 1
function call param 2
function call param 3
function call param 2
function call param 1

return fibo(n-1)+fibo(n-2);

• 2개의 fibo 함수가 다시 호출되는데, + 연산자의 왼편에 있는 fibo 함수호출이 완료되어야 비로소 + 연산자의 오른편에 있는 fibo 함수호출이 진행이 된다.

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

Binary search 알고리즘도 패턴이 반복됨을 이용해서 recursive function 형태로 만들 수 있음

패턴

• 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
• 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

탈출조건

• 탐색 범위의 시작을 의미하는 first가 탐색 범위의 끝을 의미하는 last보다 커지는 경우

함수

int BSearchRecur(int ar[], int first, int last, int target)

위의 패턴과 탈출조건, 그리고 함수 호출 형태만을 이용해 code 작성할 수 있어야 함

#include <iostream>
using namespace std;

int BSearchRecur(int arr[], int first, int last, int target)
{
	if (first > last)
		return -1; // 탐색의 실패를 의미

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

int main()
{
	int arr[] = { 1, 3, 5, 7, 9};
	int idx;

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 7);

	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 4);
	if (idx == -1)
		cout << "탐색 실패" << endl;
	else
		cout << "타겟 저장 인덱스 : " << idx << endl;

	return 0;
}

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

Q. Binary search 알고리즘을 재귀함수 기반으로 구현하는 이유는? 성능도 떨어지는데?

→ 재귀함수에 익숙해지는게 목적

하노이 타워: The Tower of Hanoi

하노이 문제

• 그림을 그려서 step by step 으로 이해
• 코드를 재귀적으로 구성
• 아래 코드와 비교

#include <iostream>
using namespace std;

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1) //이동할 원반의 수가 1개라면
	{
		cout << "원반 1을 " << from << "에서 " << to << "로 이동" << endl;
	}
	else
	{
		HanoiTowerMove(num - 1, from, to, by);
		cout << "원반 " << num << "을(를) " << from << "에서 " << to << "로 이동" << endl;
		HanoiTowerMove(num - 1, by, from, to);
	}
}

int main()
{
	//막대 A의 원반 3개를 막대 B를 경유하여 막대C로 옮기기
	HanoiTowerMove(3, 'A', 'B', 'C');
	
	return 0;
}

원반 1을 A에서 C로 이동 원반 2을(를) A에서 B로 이동 원반 1을 C에서 B로 이동 원반 3을(를) A에서 C로 이동 원반 1을 B에서 A로 이동 원반 2을(를) B에서 C로 이동 원반 1을 A에서 C로 이동