1. 함수의 재귀적 호출
함수의 재귀적 호출이란, 함수 내에서 자기 자신을 다시 호출하는 것
간단하게 이해하는 방향은 하나의 함수는 원본이 있고,
재귀호출이 발생하면, 복사본이 만들어져서 호출한다고 생각해보자.
간단한 예제를 통한 재귀 호출의 흐름
Num 3으로 시작해서 조건 검사
-> true면 호출종료, false면 num=2로 recursive 재호출
-> 종료조건 만족 시,
recursive (0) 반환 -> recursive(1)반환 -> recursive(3)반환
순서로 이어진다.
*재귀함수는 탈출조건이 필요하다.
* recursive호출을 기준으로 위 문장은 최종 반환 전 모든 함수가 반복하는 것,
recursive 후는 탈출조건 만족 후 함수가 반환을 시작하면서 반복할 문장
예제2 팩토리얼 계산
간단한 팩토리얼 계산이다.
num =5 라면
fRecursive(5)의 값은
num * fRecursive(num-1)
이를 대입해보면,
5 * fRecursive(4)
fRecusive(4)값은
4*fRecursive(3)으로 종료조건까지 이어지는 것
종료조건 fRecursive(0)에서 return을 시작하면,
리턴전에 fRecursive(0)을 호출한 fRecursive(1)->2->3 ..순으로 값을 리턴하기 시작하면서,
마지막 fRecursive(5)가 리턴하며 함수 호출을 마무리한다.
예제3 피보나치 수열
0 1 1 2 3 5의 피보나치 수열을 표현 한 것이다.
예제4 이진탐색 알고리즘의 재귀적 구현
이진탐색 알고리즘은 다음 두가지를 반복한다.
-탐색 범위의 중앙에 목표값이 저장되었는지 확인
-저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작
이진탐색 알고리즘의 종료조건은 다음과 같다.
-탐색을 종료하는 지점은 시작 위치를 의미하는 first가 끝을 의미하는
last보다 커지는 경우이다.
*재귀함수는 계산해야할 값이 커질 수록 함수의 재귀적 호출이 많아지고, 때에 따라 성능이 매우 떨어진다.
2. 하노이 타워문제
재귀함수의 대표적인 예제인 하노이 타워 문제를 풀어보자.
그림출처https://shoark7.github.io/programming/algorithm/tower-of-hanoi
A에 있는 타워를 C로 옮기는 문제이다. 제약 조건은 다음과 같다.
-한 번에 하나씩만 옮길 수 있다.
-옮기는 과정에서 작은 원반 위에 큰 원반이 올려져서는 안된다.
원반이 2개라고 가정해보자.
그렇다면 맨위에 원반을 B로 옮기고 다음 원반을 C로 옮긴 후 B의 원반을 C로 옮기면 될 것이다.
원반이 3개라면 어떨까?
A에 맨 아래 원반만 남을 때까지 가장 큰 원반을 제외한 나머지 원반(1,2)을 B로 옮기고, 가장 큰 원반(3)을 C로 옮긴 뒤 다시 B에 있는 원반(1,2)을 C로 옮기면 될 것이다. 원반이 4,5..n개 인 상태에서도 크게 보면 위와 같은 과정의 반복이다.
-하노이 타워 문제 반복패턴
맨 마지막의 1개 원반을 제외하고 나머지를 b에 옮기고, 마지막 원반을 c에 옮긴 후 다시 b->c로 나머지 원반을 옮기면 된다.
즉,
1.작은 원반들 n-1개를 a에서 b로 이동
2.큰 원반 1개를 a ->c 로 이동
3.다시 작은 원반들 n-1개를 b->c로 이동시키는 과정이다.
위와 같은 반복 패턴을 재귀로 표현해보자. HanoiTowerMove(int 원반의 갯수(n), char 시작from(A), char 중간by(B),char 최종to(C))
1. 먼저 종료 조건을 생각해보자 움직일 원반이 한 개라면, A>C로 한 개의 원반만 옮기면 그만이다.
If(num==1) { 원반 1개 A->C }
2. 다음으로 원반 n개를 C로 옮기는 과정 중 첫 번째로 해야 할 일인 n-1개의 원반을 A->B로 옮기는 과정이 필요하다.
HanoiTowerMove(n-1,from,to,by) A -> B로 n-1개의 원반을 이동
3. 다음 단계는 큰 원반을 A->C로 옮기는 단계이다.
System.out.printf(“원반 %d를 %c를 %c로 이동 \n”,num,from,to); (HanoiTowerMove의 첫 호출의 매개변수 from A, to는 C)
4. 마지막 단계는 n-1개의 작은 원반을 다시 B->C로 옮기는 과정이다.
HanoiTowerMove(n-1,by,from,to) 이를 종합하면 다음과 같이 재귀적 호출 함수를 만들 수 있다.
-------------------------------------------------------------------------------------------------------------------------------------------------
자료구조를 공부하기 전에 재귀호출에 대해 간단하게 복습 겸 몇가지 예제를 풀어보았다.
열심히 더 해야지!
참고도서: 열혈자료구조