재귀함수, 하노이의 탑

재귀함수란

함수, 메소드의 return으로 자기 자신을 호출하는 것들을 말한다.

---

재귀함수 예시, 하노이의 탑

재귀함수의 예시로 많이 등장하는 하노이의 탑이다. A칸에 있는 원반들을 B로 옮기는데, 작은 원반 위에 큰 원반이 올라올 수 없고 원반은 한번에 한개만 움직여야 한다는 것이다.

public class App {
    public void run() {
        Stack<Integer> stackA = new Stack<>();
        Stack<Integer> stackB = new Stack<>();
        Stack<Integer> stackC = new Stack<>();
        int diskNum = 3;

        for(int i = diskNum ; i > 0 ; i--){
            stackA.push(i);
        }

        System.out.println("== 현재 상황 ==");
        System.out.println(stackA);
        System.out.println(stackB);
        System.out.println(stackC);
        System.out.println("==============");

결과 :

== 현재 상황 ==
[3, 2, 1]
[]
[]
==============

자바의 스택으로 간단하게 구현한 하노이의 탑이다.

여기서 원반을 옮기는 메서드를 만드는데,

private void moveDisk(int diskNum, Stack<Integer> from,
	Stack<Integer> to, Stack<Integer> other,
    String fromName, String toName, String otherName){
    
        if(diskNum = 1){
            to.push(from.pop());
            System.out.println(fromName + "에서 " + toName +"으로 옮김.");
        }else{
            moveDisk(diskNum-1, from, other, to, fromName, otherName, toName);
            to.push(from.pop());
            System.out.println(fromName + "에서 " + toName +"으로 옮김.");
            moveDisk(diskNum-1, other, to, from, otherName, toName, fromName);
        }
    }

이렇게 만들었다.

 if(diskNum = 1){
            to.push(from.pop());
            System.out.println(fromName + "에서 " + toName +"으로 옮김.");
        }

---

먼저 옮기는 원반의 수가 1개라면 그냥 from 스택에서 to 스택으로 옮기면 된다.

else{
	moveDisk(diskNum-1, from, other, to, fromName, otherName, toName);
	to.push(from.pop());
	System.out.println(fromName + "에서 " + toName +"으로 옮김.");
	moveDisk(diskNum-1, other, to, from, otherName, toName, fromName);
}

---

1개보다 많다면 먼저 가장 아래 원반을 제외한 나머지 원반 (diskNum-1) 을 옮기는데,
여기서 다시 moveDisk 메서드를 호출하여 옮긴다.

이처럼 자신을 다시 호출하는 것이 재귀함수이다.

moveDisk(diskNum-1, from, other, to, fromName, otherName, toName);

---

그리고 가장 아래 원반을 목적지로 옮기고,

to.push(from.pop());
System.out.println(fromName + "에서 " + toName +"으로 옮김.");

---

옮겨놨던 나머지 원반을 다시 moveDisk 메서드로 목적지로 옮긴다.

moveDisk(diskNum-1, other, to, from, otherName, toName, fromName);

---

원반을 3개로 설정하면 결과는 이렇게 나오고,

A에서 B으로 옮김.
A에서 C으로 옮김.
B에서 C으로 옮김.
A에서 B으로 옮김.
C에서 A으로 옮김.
C에서 B으로 옮김.
A에서 B으로 옮김.

원반 3개가 스택 B로 옮겨진 것을 확인 할 수 있다.

== 현재 상황 ==
[]
[3, 2, 1]
[]
==============