재귀

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) 이를 종합하면 다음과 같이 재귀적 호출 함수를 만들 수 있다.

-------------------------------------------------------------------------------------------------------------------------------------------------

자료구조를 공부하기 전에 재귀호출에 대해 간단하게 복습 겸 몇가지 예제를 풀어보았다. 

열심히 더 해야지! 

 

참고도서: 열혈자료구조