[자료구조] 2. 재귀함수

 

 

 

* 본 포스팅은 윤성우의 열혈 자료구조론을 읽으며 공부한 내용을 정리한 글입니다.

저의 부족한 생각과 주관으로 틀린 내용이 있을 수 있으니, 자세한 내용이 궁금하시다면 해당 책을 읽어보시길 추천드립니다.

 

 

 

 

---

 

목차

1. 함수의 재귀적 호출의 이해

2. 재귀의 활용

3. 하노이 타워

---

1. 함수의 재귀적 호출의 이해

재귀함수란?

함수 내에서 자기자신을 다시 호출하는 함수입니다.

그럼, 완료되지 않은 함수룰 다시 호출하는걸까요?

입니다. 새로 메모리를 할당하여 복사본을 만들어서 실행시키는거라 아무 문제 없습니다.

단, 탈출구를 만들지 않으면 무한 재귀호출로 문제가 생기게 됩니다.

몸풀기로 팩토리얼을 수식으로 구현해 보겠습니다.

앗! n!를 전개하면 (n-1)! 부분에서 또 팩토리얼식이 나오네요! 이부분이 재귀함수로 구현이 되겠죠?

그러면 탈출조건은 위 식이 성립하는 조건에 위배될 떄겠죠? 조건을 살펴봅시다.

따라서, 탈출조건은 0!이 1이므로, 이게 탈출 조건입니다.

이걸 코드로 옮겨보면 아래와 같습니다.

private int fac(int n){
	if (n == 0){
		return 1;
	} else (n >= 1){
		return n * fac(n - 1)
	}
}

 

2. 재귀의 활용

피보나치 수열부터 살펴보겠습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 66 …

위의 규칙은 “현재의 수는 앞의 두수를 더한 값” 입니다.

→ 이는 수열의 n번째 값 = (n-1번째 값) + (n-2번째 값) 이며,

fib(n)에 대하여, 아래가 성립한다.

이걸 코드로 구현해보면,

 

//단, n은 1 이상의 정수 (0번째는 존재하지 않으므로 제외한다)
private int fibo(int n){
	if( n == 1) return 0;
  if( n == 2) return 1;
  return fibo(n-1) + fibo(n-2);
}

 이 코드는 단순히 피보나치 수열의 n번째 수를 나타낼 뿐입니다.

해당 fibo 함수를 활용해서 1번쨰부터 10번째까지의 수을 나열하려면, 반복문을 활용하면 되겠죠?

for(int i = 1; i <= 10; i++){
	system.out.println(fibo(i));
}

 재귀함수를 처음 배운다면, 호출순서에 대해 이해가 쉽지 않아 

코드를 이해했다고 생각하지 않거나 찜찜해 하실수도 있습니다.

이런분들을 위해 저자는 이런말을 하더라구요.

수열을 수학적 수직을 표현해 이를 코드로 구현했으며 해당 과정에 문제나 이해되지 않은 부분이 없다면,

코드를 완전히 이해한 것이라고.

호출순서는 결국 재귀함수에 익숙해지면 신경이 쓰이지 않게 된다고…

 

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

 물론, 재귀적으로 구현하면 반목문보다 효율이 좋지 않지만, 이해를 위해 소개해 드리겠습니다.

이진탐색 알고리즘은 아래와 같은 과정의 반복이죠?

1. 중앙값을 찾는다
2. 탐색 목표가 중앙값이 아니라면, 탐색범위를 재지정한다

여기서 이진탐색의 네가지 파라미터가 모두 결정되었습니다.

탐색의 대상, 탐색범위의 시작, 탐색범위의 끝, 탐색 목표 입니다.

private int BSerachRecur(int[] ar, int first, int last, int taget){

}

그리고 재귀의 탈출 시점은 ‘first(탐색 시작위치) > last(탐색 끝 위치) 일 경우입니다.

private int BSerachRecur(int[] ar, int first, int last, int taget){
	if(first > last)
		return -1; // 탐색이 성공했으면 나올수없는값으로, 실패값이라 약속
}

필요한 파라미터와 재귀 탈출부를 얻었으니 이제 이진탐색 알고리즘을 구현해볼 차례죠?

private int BSerachRecur(int[] arr, int first, int last, int taget){
	if(first > last)
		return -1; // 탐색이 성공했으면 나올수없는값으로, 실패값이라 약속
	
	//1. 중앙값을 찾는다.
	int mid = (first + last) / 2;
	
	//2. 탐색 목표가 중앙값이 아니라면, 탐색범위를 재지정한다.
	if (arr[mid] == target) return mid;
	if (target < ar[mid]){
		return BSerachRecur(ar, first, mid-1, target);
	} else {
		return BSerachRecur(ar, mid+1, last, target)
	}
}

3. 하노이 타워

 워낙 유명한 문제라, 다들 규칙은 알고 있을거라 생각해 간략히 설명하겠습니다.

하노이 타워란, 하나의 막대에 쌓여 있는 원반을 다른 하나의 원반에 그대로 옮기는 방법을 설명하는 문제입니다.

단, 규칙은 “원반은 한번엔 하나씩만 옮길 수 있으며, 옮기는 과정에서 작은 원반 위에 큰 원반이 올라올 수 없다” 입니다.

원반의 수가 늘어나도 일련의 과정을 더 많이 반복하게 뒤므로, 재귀로 표현하기 딱입니다.

자, 막대 A에 꽂힌 원반 n개를 막대 C로 옮기는 과정은 아래와 같습니다.

1. 작은 원반 n-1개를 A에서 B로 이동시킨다
2. 큰 원반 한개를 A에서 C로 이동시킨다
3. 작은원반 n-1개를 B에서 C로 이동시킨다.

 이렇게 되면 원반 n개를 이동하는 문제가 n-1를 이동하는 문제로,
n-1개를 이동하는 문제는 (n-1)-1개를 이동하는 문제로 …
세분화 하다보면 결국 원반 1개를 이동하는 문제로 도달하게 된죠. 바로 재귀로요!

 

원반의 갯수, ‘A’에서 ‘B’를 거쳐 ‘C’로 원반을 이동시키므로

private void hanoi(int num, char from, char by, char to){

}

위의 형태가 됩니다.

 

그럼 이제, 로직도 알고 매개변수도 구했으니 하나만 더 찾으면 코드로 옮길 수 있습니다!

바로 재귀 탈출 조건이요!

n개의 원반을 옮기는 문제가 1개의 원반을 옮기는 문제까지 세분화 되므로,

옮길 원반이 1개일때가 재귀의 탈출조건입니다.

private void hanoi(int num, char from, char by, char to){
	if(num == 1){
		system.out.println("원반 하나를 " + from + "에서 " + to + "로 이동했습니다.");
		return;
	}
	//1. 작은원반 n-1개를 A에서 B로 이동시킨다.
	hanoi(num - 1, from, to, by);
	//2. 큰 원반 한개를 A에서 C로 이동시킨다.
  printf("원반 " + num + "을 " + from + "에서 " + to + "로 이동했습니다.");
	//3. 작은원반 n-1개를 B에서 C로 이동시킨다.
	hanoi(num-1, by, from, to);
}