160109P(토)

자료구조 Chapter 9 - 재귀

 

재귀

어떤 개념을 정의할 때 정의하고 있는 그 개념 자체에 대한 정의 내부에 자기 자신이 포함되어 있는 경우

 

재귀정의(recursive definition)

개념 자체에 정의된 재귀

 

재귀적 호출

중복적이거나 반복적인 호출을 수행할 때 자기 자신에 대한 호출이 함수 자체에 포함되어 있는 것

 

직접 순환(directed recursion)

프로그램에서 함수가 직접 자신을 호출하는 것

 

간접 순환(indirected recursion)

다른 제 3의 함수를 호출하고 그 함수가 다시 자신을 호출하는 경우

 

기본경우(base case)

자기 자신을 다시 호출하지 않고 현재 단계에서 문제를 해결하고 값을 반환 할 수 있는 경우

모든 재귀적 방법은 무한재귀를 피하기 위해서 기본 경우를 가지고 있어야 한다.

 

// 기본경우

if(초기조건) {

문제해결;

}

 

else

간단한 경우를 만들기 위해 자기 자신 다시 호출

 

삼각수(Triangular Number)

1, 3, 6, 10, 15, 21...과 같이 첫번째 단계에서는 1로 시작하여 다음단계에서는 이전 단계에서의 값과 현재 단ㄷ계를 더하여 값을 구한다.

 

첫번째

1

 

두번째

1 + 2 = 3

 

세번째

3 + 3 = 6

(1 + 2) + 3 = 6

 

네번째

6 + 4 = 10

((1 + 2) + 3) + 6

.

.

.

 

조건 1

1번째 단계의 값은 1이다.

 

조건 2

n > 1인 단계의 값은 n - 1 단계에서의 값과 n 단계의 합을 구한다.

 

loop

int triLoop(int n) {

int tot = 0;

 

while(n > 0) {

tot = tot + n;

 

--n;

}

 

return tot;

}

 

재귀

int triRec(int n) {

if (n == 1) {

return 1;

}

else {

return(n + triRec(n - 1));

}

}

 

효율성

메소드 호출은 오버헤드와 연관된다.

메소드에 대한 인자와 메소드가 반환될 위치를 가리키는 주소는 반드시 컴퓨터 내부 스택에 삽입

∴ loop가 재귀보다 빠르다.

 

순차곱셈(factorial)

n!

 

n = 0

n! = 1

 

n >= 1

n! = n * (n - 1) * ... * 2 * 1

 

public static int factorial(int n) {

if(n == 0) {

return 1;

}

else {

return (n * factorial(n - 1));

}

}

 

피보나치 수열(Fibonacci sequence)

이전 수와 이전 수의 합으로 만들어 진다.

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

 

n = 0

f0

 

n = 1

f1

 

n >= 2

fn = f(n - 1) + f(n - 2)

 

public static int fibonacci(int n) {

if(n == 0) {

return 0;

}

else if(n == 1) {

return 1;

}

else {

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

}

}

 

재귀적 이진탐색

public int findRec(long searchKey, int lowerBound, int upperBound) {

int curIn;

 

curIn = (lowerBound + upperBound) / 2;

 

if(a[curIn] == searchKey) {

return curIn;

}

else if(lowerBound > upperBound) {

return nElems;

}

else {

if(a[curIn] < searchKey) {

return findRec(searchKey, curIn + 1, upperBound);

}

else

return findRec(searchKey, lowerBound, curIn - 1);

}

}

 

하노이의 탑(Towers of Hanoi)

규칙 1

원판은 한번에 하나씩 현재 기둥에서 바로 이웃한 기둥으로 원판을 옮길 수 있다.

 

규칙 2

이웃 기둥에 원판이 존재하면 그 다음 기둥으로 원판을 이동

 

규칙 3

기둥에 옮겨진 원판은 위의 원판이 아래의 원판보다 작아야 한다.

 

하위트리(subtree)

하나의 커다란 문제를 조그만 문제로 나눠서 해결

divide and conquer 알고리즘

원판을 하나씩 이동하는것이 아닌 하위트리로 쪼개서 덩어리를 옮기되 실제 내부 동작은 다시 조그만 문제로 분할해서 해결

 

public static void moveDisk(int top, char from, char mid, char to) {

if(top == 1) {

System.out.println("원판 1이 기둥" + from + "에서 기둥" + to + "로 이동");

}

else {

moveDisk(top - 1, from, to, mid);

 

System.out.println("원판" + top "이 기둥" + from + "에서 기둥" + to + "로 이동");

 

moveDisk(top - 1, mid, from, to);

}

}