알고리즘)재귀호출

재귀호출

자기자신을 호출한다.

재귀적으로 문제를 해결함은 또 문제를 점점 더 작은 단위로 쪼개어 해결함을 의미한다.

잘못된 재귀 호출

문제 해결에 변화없는 호출

void rose()

{ rose(); }

무한루프 -> 시스템 내부의 스택에 복귀주소와 인자를 저장해야 하기 때문에

스택에는 자료가 쌓인다.

재귀 호출의 요건

재귀호출이 이루어질 때마다 문제는 점점 작아져야 하고,

재귀 호출이 끝이 나는 종료 조건이 있어야 한다.

1. 거듭제곱을 구하는 재귀 함수

N의 거듭 제곱은 N!이라고 표현한다.

ex) 4를 넣었을때

4 x(3 x(2 x(1 ))) = 24

//0! 되면 재귀함수 탈출

2. 피보나치 수열 구하는 재귀 함수

한 함수 내에서 한번만 이루어져야 하는 것은 아니다.

한 함수 내에서 두 번 혹은 그 이상도 자기자신을 호출할 수 있다.



3. 하노이의탑

세 개의 기둥과 서로 다른 크기의 N개의 원반으로 구성된다. 이 원반들은 세 개의 기둥 중의 하나에 반드시 꽂혀 있어야하며, 자신보다 작은 원반 위에는 그 원반을 놓을 수 없다.

즉 원반은 아래에 가장 큰 것이 와야하며, 자신보다 큰 원반은 자기 위에 놓을 수 없다.

N이 3일때

1. 기둥 1의 원반을 기둥 3으로 옮긴다

2. 기둥 1의 원반을 기둥 2로 옮긴다.

3. 기둥 3의 원반을 기둥 2로 옮긴다.

4. 기둥 1의 원반을 기둥 3으로 옮긴다.

5. 기둥 2의 원반을 기둥 1로 옮긴다.

6. 기둥 2의 원반을 기둥 3으로 옮긴다.

7. 기둥 1의 원반을 기둥 3으로 옮긴다.

재귀적 표현

1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.

2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.

3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

원반 n개 , from 기둥에서 to 기둥으로 by기둥을 이용해서 옮기는 과정

           void hanoi(int n, int from ,int by, int to)

           {

               if (n == 1)

               {

                   move(from, to);

               }

               else

               {

                   hanoi(n - 1, from, to, by); //알고리즘 1번

                   move(from, to);        //알고리즘 2번

                   hanoi(n - 1, by, from, to); //알고리즘 3번

               }

           }

           void move(int from, int to)

           {

               Console.WriteLine(string.Format("{0}에서~{1}로 ",from,to));

           }

<결과>