[알고리즘] 재귀함수 (예제:하노이 탑-Java)

ㅁ 재귀함수

- 자기 자신을 호출하는 함수

- 자기 자신을 호출하여 더 작은 문제를 풀게 하여 문제를 해결하는 방법

- 중요한 것은 종료해야만 한다는 것

 

ㅁ 재귀 사용 목적

- 배귀는 반복 코드보다 짧고 작성하기 쉽다.

- 일반적인 루프는 컴파일될 때 재귀함수로 바뀐다.

- 비슷한 하위 작업으로 정리될 수 있는 작업에 특히 유용(예:정렬, 검색, 탐색)

 

ㅁ 메모리

- 재귀 호출시마다 메서드는 복사본(실제는 변수만)이 메모리에 만들어진다

- 메서드가 종료될 때마다 복사본은 메모리에서 삭제된다.

- 재귀 방법은 쉬워 보이지만 시각화와 추적에 시간이 걸린다.(코드를 읽기가 어렵다)

 

ㅁ 재귀와 반복

- 일반적으로 재귀 방법은 접근이 어려운 문제를 쉽게 풀 수 있게 해 준다.

- 매번 수행하는 재귀 호출에 부가적인 요소들이 (스택 공간:함수 호출 시 인사 들) 추가된다.

* 재귀

- 기본 경우에 도달하면 종료

- 각 재귀 호출은 스택 등 부가적인 공간이 필요

- 무한 재귀에 들어가면 메모리 용량 소비 또는 오버플로우 발생

- 재귀적인 방법이 쉬운 문제들이 있음

* 반복

- 조건이 거짓일 때 종료

- 각 반복이 부가 공간을 필요로 하지 않는다.

- 무한 루프는 추가 메모리 공간을 필요로 하지 않아 무한 반복

- 재귀 방법에 비해 간단하지 않을 때가 있다.

 

public class Hanoi {

 /**
  * @param args
  */
 public static void main(String[] args) {
  /*if (args.length<1) {
   System.out.println("Usage : java HanoiTab number ");
   System.exit(1);
  }
  
  int value = Integer.parseInt(args[0]);
  */
  int value = 3; //테스트를 위해서 원반수 지정
  Hanoi h = new Hanoi();
  h.hanoiTab(value, 'A', 'B', 'C');
 }

 //n : 원반의 수, a:이동전기둥, b:사용기둥, c:이동후 기둥
 void hanoiTab(int n, char a, char b, char c ) {
   if (n>0) {
    hanoiTab(n-1, a, c, b);
    System.out.println(n + "번째 원반을 " + a + "에서 " + c + "로 이동");
    hanoiTab(n-1, b, a ,c);
   }
 }
}

 

* 결과

1번째 원반을 A에서 C로 이동
2번째 원반을 A에서 B로 이동
1번째 원반을 C에서 B로 이동
3번째 원반을 A에서 C로 이동
1번째 원반을 B에서 A로 이동
2번째 원반을 B에서 C로 이동
1번째 원반을 A에서 C로 이동