재귀호출 - 알고리즘

오늘은 재귀호출에 대해 알아보도록 하겠습니다. 알고리즘에서 배우는 내용이기는 한데 그렇게 많이 쓰이지는 않습니다. 하지만 재귀호출이 아니면 프로그래밍이 너무 어려워지는 경우들이 있습니다. 재귀호출은 중요한 개념이고 이것을 배움으로써 프로그램에서 함수(자바에서는 메소드)가 어떻게 호출되는지 어떻게 사용되는지 알 수 있습니다. 우선 기본적으로 재귀호출(recursion)은 자기가 자신을 부르는 것이고 반드시 조건문에 의해 종료가 되어야 합니다. 우선 팩토리얼에 대해 알아보겠습니다. 

수학에서 n! = n * (n - 1) * (n - 2) * ... * 1입니다. 이것은 다시 n! = n * (n - 1)!로 정의할 수 있습니다. 이것처럼 n!을 (n - 1)!을 이용해서 값을 구할 수 있다면 !를 함수로 생각한다면 재귀호출이 되는 것입니다. 우선 프로그램을 보면서 설명하도록 하겠습니다.

위의 프로그램에서는양수의 값을 입력받기위해 Scanner객체를 사용했으며 do while문을 사용했습니다. 일단 양수의 값을 받고 난 다음에는 factorial이라는 메소드를 호출했습니다. 매개변수는 입력받은 양수값을 전달했습니다. factorial이라는 메소드에서 볼 수 있듯이 재귀호출 메소드의 시작은 재귀호출을 빠져나가기 위한 조건문으로 되어있습니다. 이 조건문을 잘못 작성하거나 빠뜨린 경우는 무한루프에 빠지게 되어 프로그램이 종료하지 않게 됩니다. 그렇기때문에 빠져나가기 위한 조건문은 굉장히 중요합ㄴ니다. 위의 예에서는 미리 양수를 걸러내어 매개변수로 넘겼기때문에 위의 조건만으로도 가능했으나 그렇지 않다면 0보다 적은 조건에 대한 조건문이 존재해야합니다. 이와 같은 팩토리얼을 구하는 예제는 단순히 알아보기 쉽게 하기 위한 것이지만 실제로는 for문을 이용해서 구현하면 훨씬 더 쉽게 효율적인 프로그램을 작성할 수 있습니다. 하지만 쉬운 예제를 통해 재귀호출을 이해한다면 일반적인 for나 while문으로 처리하기 어려운 경우에 재귀호출을 사용할 수 있게 됩니다. 일단 for문을 사용하여 위의 예제를 변형해 보았습니다.

이와 같이 for문을 사용해도 같은 결과를 얻을 수 있습니다. 이 경우는 훨씬 더 간단하고 효율적입니다. 사실 재귀호출이 효율적이지는 않습니다. 하지만 어려운 프로그램을 쉽게 작성할 수 있도록 해주고 이해하기 쉬운 코드로 작성할 수 있게 해줍니다.

이제 본격적으로 재귀호출을 제대로 사용할 수 있는 예제를 알아보도록 하겠습니다. 일반적으로 재귀호출이라고 하면 하노이타워 프로그램을 작성하는 예제를 많이 사용합니다. 이것만 제대로 이해하면 재귀호출에 대해 완벽하게 이해하게 됩니다. 일단은 하노이타워 프로그램이 무엇인지부터 알아봐야 겠습니다. 하노이 타워 프로그램은 시작점에 있는 n층타워를 목적지로 옮기려고 하는데 전재조건이 있습니다. 한번에 하나의 층만 옮길 수 있고 작은 탑위에 큰 탑을 놓을 수는 없습니다. 그래서 시작점과 목적지외에 중간지점이 존재하게 됩니다.  일단은 제일 쉬운 2층타워를 예로 들어보겠습니다. 2층타워라고해도 2개의 층이 있기때문에 한번에 옮길 수는 없습니다. 제일 위의 층을 바로 목적지에 옮기게 되면 다음의 더 커다란 층을 목적지 위에 올릴 수 없게 됩니다. 그래서 제일 위의 층을 중간지점에 먼저 옮긴 후 마지막 층을 목적지로 옮기고 중간지점에 있는 제일 작은 층을 목적지로 옮기면 됩니다. 이 하노이 타워도 아까의 팩토리얼처럼 재귀호출 형식으로 만들어야 합니다. 팩토리얼은 n! = n * (n - 1)!형태로 만들어서 재귀호출을 사용할 수 있었습니다. 하노이 타워도 마찬가지로 메소드에서 메소드를 호출할 수 있는 형태로 만들어야 합니다. 재귀호출 프로그램을 작성하려면 메소드에서 다시 메소드를 호출하는 형태의 개념으로 만들어야 합니다. 위의 하노이 타워의 경우에는 시작점에서 (n - 1)개를 중간지점으로 옮긴다음 마지막 1개를 시작점에서 목적지로 옮기고 다시 (n-1)개를 중간지점에서 목적지로 옮기면 됩니다. 여기서 옮기는 것을 메소드로 지정하면 됩니다.

위의 프로그램은 어떤 순서로 옮기는지를 출력하는 것입니다. Start는 출발지, Middle은 중간지점, Dest는 목적지입니다. 앞에서 설명드렸듯이 빠져나오기위한 기본조건을 처음에 두었고 자기자신을 부르는 재귀호출을 하였습니다. hanoi(height - 1, start, dest, middle)로 재귀호출을 하면 계속 height에서 1을 감하게되어 나중에 1에 이르게 되는 것입니다. 원래 제대로 하려면 조건문에서 1보다 작은 것에 대해 에러를 출력하는 문장을 넣어야하지만 위의 프로그램은 단순히 예제이므로 생략했습니다. 설명이 장황하여 여러분이 잘 이해하셨을렸는지는 모르겠으나 천천히 읽어보시고 프로그램을 보시면 이해하실 수 있을 것입니다. 위의 프로그램에서 핵심은 height - 1을 start에서 middle로 옮기고 하나를 start에서 dest로 옮긴 후 middle에 있는 height - 1을 dest로 옮기는 것입니다.