[Java] 자바로 프로그래밍 입문하기: 2.3. 재귀 (1)

재귀

  우리는 이제껏 한 함수에서 다른 함수를 호출해왔습니다. 만약 어떤 함수가, 자기 자신을 호출하는 건 어떨까요? 자바를 비롯한 대부분의 현대 프로그래밍 언어들은 이런 메커니즘을 제공하고 있습니다. 바로 재귀(recursion)입니다. 이번 절에서 우리는 다양한 문제를 세련되고 효율적으로 해결하는, 재귀에 대해 알아볼 것입니다.

  재귀를 사용하면, 더 간편하고 쉽게 이해할 수 있는 프로그램을 만들 수 있습니다. 재귀에 익숙하여 코드에 일상적으로 재귀를 사용할 수 있는 프로그래머들은 사실 흔치 않습니다. 하지만 재귀로 어떤 문제를 우아하게 해결해내는 경험은, 많은 프로그래머들과 심지어 여러분들에게도 귀중한 경험입니다.

재귀 나무

  재귀라 함은 꼭 프로그래밍 기법만은 아닙니다. 자연 세계에서도 이는 손쉽게 찾아볼 수 있죠. 재귀 나무는 보다시피 실제 나무를 닮았습니다. 수많은 자연 현상들은 재귀로 표현될 수 있습니다. 다시 말해 재귀를 통한다면, 현실의 수많은 문제들을 해결할 수 있습니다.

  이는 재귀를 이용해야 하는 중요한 이유 중에 하나입니다. 굉장히 어려운 수학 문제도, 재귀를 이용하면 직관적이고 쉽게 풀리는 경우가 있습니다. 바로 수학적 귀납법(mathematical induction)에 대한 이야기입니다. 수학 공부 시간이 아니니, 수학적으로 자세히 다루진 않겠지만 재귀는 이 때 굉장히 강력한 힘을 발휘한다는 사실을 기억하세요.

첫 재귀 프로그램

  재귀의 <HelloWorld>는 바로 팩토리얼 함수입니다. N!은 N부터 1까지의 곱입니다. N!을 어떻게 계산할 수 있을까요? 우리는 for문을 이용해 쉽게 계산할 수 있을 것입니다. 하지만 이번 시간에는 재귀로 이를 해결해보죠.

public static long factorial(int N) { if (N == 1) return 1; return N * factorial(N-1); }

  이 정적 메소드는 자기 자신을 호출합니다. 또한 팩토리얼을 완벽히 계산해내죠. 심지어 이 메소드를 자세히 보면, N=1일 때 1을 반환한다는 것 말고는 딱히 무언가를 하지 않는다는 것도 알 수 있습니다. 이는 다음의 위대한 등식에 의해서 가능하게 된 것입니다.

  factorial(5)를 계산하기 위해, 재귀 메소드는 5*factorial(4)를 반환합니다. factorial(4)를 계산하기 위해, 재귀 메소드는 4*factorial(3)을 반환하게 됩니다. 마지막에 factorial(1)은 비로소 숫자 1을 반환하게 되죠. 다음의 함수 호출 추적 테이블을 참고 하세요.

  우리의 factorial() 구현은, 재귀 함수를 만들기 위해 두 가지의 구성이 필요하다는 것을 알려줍니다. 

  첫째, 재귀적인 호출을 더이상 만들어내지 않는 base case가 필요합니다. 이는 하나 이상의 특별한 입력값에 대해 재귀 없이 값을 반환하게 됩니다. factorial()의 경우, base case는 N=1이었습니다. 

  둘째, 재귀 함수의 중심인 reduction step입니다. 이는 해당 함수의 입력을, 또 다른 함수의 입력으로 대체하게 됩니다. factorial()의 경우, reduction step은 N*factorial(N-1)이었습니다.

  모든 재귀 함수는 이 두가지의 구성이 반드시 필요합니다. 또한, 재귀되어 호출되는 매개변수 값들은 전부 base case에 도달해야 합니다. factorial()의 경우, 양의 정수라면 어떤 N이든 전부 N=1에 도달했을 것입니다.

수학적 귀납법

  재귀적 프로그래밍(recurisve programming)은 수학적 귀납법과 굉장히 밀접한 관계입니다. 수학적 귀납법이란, 증명 방법 중 하나입니다. 무한하게 많은 정수 N에 대해서 일일히 증명을 할 수 없으니 대신 사용하는 방법입니다.

• Base case: 특정 값에 대해서 구문이 참임을 증명합니다. (보통 1)
• Induction step: N에 대해서 구문이 참이라고 가정했을 때, N+1 또한 참임을 증명합니다.

  이 두 단계를 완수한다면, 결국 모든 N에 대해서 참임이 증명됩니다. 1에 대해서 참임을 증명 했으므로 N+1인 2 또한 참일 것이고, 이를 반복해서 무한하게 모든 자연수에 대해 참임이 증명되는 것입니다. 

  우리가 재귀적인 프로그램을 작성할 때마다, 원하는 결과를 얻기 위해서는 이 수학적 귀납법을 적용해보아야 합니다. 귀납과 재귀는 완벽하게 일치합니다. 다만 문제를 바라보는 시각이 다르죠. 재귀는 큰 문제를 작은 문제로 쪼개나가는 반면, 귀납은 작은 문제를 큰 문제로 확장해 나갑니다.

프로그램 2.3.1: Euclid's algorithm

public class Euclid { public static int gcd(int p, int q) { if (q == 0) return p; return gcd(q, p % q); } public static void main(String[] args) { int p = Integer.parseInt(args[0]); int q = Integer.parseInt(args[1]); int d = gcd(p, q); StdOut.println(d); } }

% java Euclid 1440 408
24
% java Euclid 314159 271828
1

gcd의 함수 호출 추적 테이블

유클리드 호제법

  최대공약수는 두 정수를 나누어 떨어지게 하는 수 중 가장 큰 정수를 의미합니다. 가령 102와 68의 최대공약수는 34죠. 이 최대공약수를 어떻게 찾을 수 있을까요? 아마 여러분은 소인수분해를 통해서 최대공약수를 찾는 방법에 대해 배웠을 것입니다. 큰 수의 최대공약수를 찾는 것은 암호화에서 중요한 문제죠.

  우리는 다음 사실을 통해서 p와 q의 최대공약수를 수월하게 계산할 수 있습니다.

• 만약 p>q라면, p와 q의 최대공약수는 q와 p%q의 최대공약수와 같다.

  이는 조금 직관적으로 이해하기 어려울 수도 있습니다. 먼저, p와 q의 최대공약수는 q와 p-q의 최대공약수와 동일하다는 사실을 스스로 납득해보세요. q와 p-2q, q와 p-3q 역시 마찬가지입니다. 좀더 빠른 속도로 계산 하려면 가장 작은 양의 정수인 q-nq를 찾아내는 것이 중요할 것입니다. 그것이 바로 p%q입니다.

  <Euclid>는 최대공약수의 속성을 이용한 재귀함수로 간편하게 기능을 구현하고 있습니다. base case는 q가 0일 때, 즉 gcd(p, 0) = p의 경우입니다. reduction step이 곧 base case로 수렴하는 것을 관찰해보세요. 만약 p<q의 경우, 처음 재귀 단계 때 p와 q가 자연스럽게 바뀌게 됩니다. 이 재귀적 해결책은 유클리드 호제법이라는 이름으로, 2000년이 넘은 알고리즘 중 하나입니다.

하노이의 탑

  재귀를 다루기 위해서 빼놓을 수 없는 문제가 있습니다. 바로 하노이의 탑입니다. 세 개의 기둥과 크기가 각기 다른 n개의 원판이 있습니다. 한 기둥에 원판들이 모두 쌓여 있으며, 가장 아래에는 크기가 가장 큰 원판부터, 위로 갈수록 크기가 작은 원판들로 잘 정렬되어서 쌓여 있습니다. 우리는 이 원판들을 다른 기둥으로 다시 쌓아올리고 싶습니다. 원판을 옮기는데에는 규칙이 있습니다.

• 한 번에 한 원판만 옮길 수 있다.
• 작은 원판 위에 크기가 더 큰 원판을 놓을 수 없다.

하노이의 탑

  전설에 따르면, 64개의 황금 원판과 세 개의 다이아몬드 기둥이 있는 사원에서 수도승들이 이 작업을 완료하면, 세상은 멸망한다고 합니다. 하지만 이 문제를 어떻게 해결할 수 있을까요?

  이 문제를 해결하기 위한 우리의 목표는 원판을 옮기는 일련의 원칙을 만들어내는 것입니다. 각 원판은 크기에 따라 숫자로 지칭하고, 왼쪽으로 옮길지 오른쪽으로 옮길지 정하도록 해보죠. 만약 원판이 왼쪽 기둥에 있다면 왼쪽으로 옮기는 명령은 오른쪽 끝으로 옮기는 것으로 생각합니다. 만약 원판이 오른쪽 기둥에 있다면 오른쪽으로 옮기는 명령은 왼쪽 끝으로 옮기는 것으로 생각합니다. 이는 기둥이 원형으로 배치되어 있다고 생각하면 직관적이겠네요.

  만약 모든 원판이 한 기둥에 있을 때에는 두 가지 이동이 가능할 것입니다. 가장 작은 원판을 왼쪽이나 오른쪽으로 옮기는 것이죠. 그 외의 경우에는 세 가지 이동이 가능합니다. 가장 작은 원판을 왼쪽이나 오른쪽으로 옮기는 것과, 나머지 기둥에서 규칙에 위배되지 않는 이동이 하나 가능할 것입니다.

  여러 가능한 움직임 중에, 우리의 목표를 달성할 수 있는 방법을 어떻게 선택할 수 있을까요? 재귀를 이용한 아이디어를 생각해보죠. 가장 큰 원판이 다른 기둥으로 옮겨지기 위해서는, 나머지 n-1개의 원판들이 한 기둥에 쌓여있어야 합니다. 그리고 가장 큰 원판을 옮겼다면, 나머지 n-1개의 원판들을 어찌저찌 그 위에 올리면 되죠. 다음 절차와 그림을 통해 이해해보세요.

1. n-1개의 원판을 오른쪽으로 옮깁니다.
2. 가장 큰 원판을 왼쪽으로 옮깁니다.
3. n-1개의 원판을 오른쪽으로 옮깁니다.

하노이의 탑을 위한 재귀 전략

  <프로그램 2.3.2, TowersOfHanoi>는 단순히 이 전략을 구현했을 뿐입니다. 한 번 확인해보시죠.

프로그램 2.3.2: Towers of Hanoi

public class TowersOfHanoi { public static void moves(int n, boolean left) { if (n == 0) return; moves(n - 1, !left); if (left) StdOut.println(n + " left"); else StdOut.println(n + " right"); moves(n - 1, !left); } public static void main(String[] args) {                 // Read n, print moves to move n discs left. int n = Integer.parseInt(args[0]); moves(n, true); } }

% java TowersOfHanoi 1
1 left

% java TowersOfHanoi 2
1 right
2 left
1 right

% java TowersOfHanoi 3
1 left
2 right
1 left
3 left
1 left
2 right
1 left

  <TowersOfHanoi>는 n을 명령행 인자로 받아 n개의 원판이 있는 하노이의 탑 문제에 대한 해결책을 제시합니다. 재귀 정적 메소드인 moves()는 해당 원판을 왼쪽으로 옮길지 오른쪽으로 옮길지에 대해 제시합니다. 이는 우리가 생각한 계획에 따라 정확히 수행됩니다.

함수 호출 트리

  <TowersOfHanoi>와 같이 많은 재귀 호출이 이루어지는 모듈화 프로그램의 행위를 좀 더 잘 이해하기 위해, 이들을 시각적으로 표현한 함수 호출 트리라는 것을 소개해드릴까 합니다. 특히, 우리는 각 메소드의 호출을 트리의 노드로 재현할 수 있습니다. 각 노드에는 원 안에 인자의 값들이 포함됩니다. 마지막으로, 선이 노드들을 연결하고 있죠.

  이 함수 호출 트리만 있다면 프로그램의 행위를 이해하는 것은 식은 죽 먹기입니다. 어떤 종류의 프로그램이든 간에 함수 호출 트리로 표현할 수 있지만, 재귀 프로그램의 행위를 나타내고자 할 때 그 위력을 발휘합니다. 다음 그림에서 트리의 노드는 <TowerOfHanoi>에서 각자 move()를 호출하는 것에 대응하며, 그리기도 쉽습니다.

<TowerOfHanoi> moves(4, true)의 함수 호출 트리

  한 번 직접 그려봅시다. 트리 노드 안에는 옮겨야 할 원판의 개수, 그리고 옮겨야 하는 방향이 적혀 있습니다. 방향은 코드 상에서 boolean 값이지만, 보기 편하기 위해서 화살표로 표시하였습니다. 그리고 아래에 두 개의 트리 노드를 더 그리는 것입니다. 원판의 개수는 하나 감소시키고, 방향은 전환되며, 이런 식으로 1이 될 때까지 반복합니다. 즉, 노드 하나는 moves()의 호출 하나에 대응합니다.

moves(4, true)의 함수 호출 추적 테이블

  잠깐 위의 그림을 보며 이해하는 시간을 가져봅시다. 함수 호출 트리는 결국 추적 테이블을 좀 더 간편하게 나타내는 도구에 불과함을 깨달을 수 있을 것입니다. 특히, 함수 호출 트리에서 각 노드들을 왼쪽부터 오른쪽으로 순서대로 읽어보면, 이것이 곧 문제를 해결하는 방법임을 알 수 있습니다.

  또한 여러분이 트리를 유심히 보면, 다음과 같은 두 가지 규칙이 보일 것입니다.

• 한 원판을 움직이면, 반드시 그 다음에는 가장 작은 원판을 움직입니다.
• 그 원판은 언제나 같은 방향으로 움직입니다.

  우리는 이런 관찰을 통해서, 재귀 없이도 이 문제를 해결할 수 있게 됩니다. 가장 작은 원판을 움직이면, 그 다음 다른 원판이 움직일 수 있는 곳은 사실 단 한 곳밖에 없습니다. 우리는 이 방법을 통해 재귀 프로그램과 같은 결과를 만들어낼 수 있음을 증명할 수 있습니다. 까마득한 기원전, 컴퓨터가 없을 때 수도승들은 재귀 대신 이 방법을 이용했겠네요.

  트리는 재귀를 이해하는 데 아주 중요합니다. 트리는 그 자체로 재귀적인 객체이기 때문입니다. 추상 수학적 모델로서, 트리는 다양한 응용프로그램에서 중요한 역할을 차지지합니다. 트리의 개념은 나중에 배워볼 수 있겠지만, 지금 본 것을 잊지는 마세요.

지수적 시간(Exponential Time)

  재귀를 사용함으로써, 우리는 재귀 프로그램의 동작에 대한 중요한 사실을 증명할 수 있게 도와주는 수학적 모델을 개발할 수 있습니다. 하노이의 탑의 경우, 우리는 세상이 종말하는 데 걸리는 시간을 계산해볼 수 있죠.(물론, 전설이 사실이라면 말입니다) 이는 세상이 종말이 한참 멀었음을 알려주기에 중요한 것이 아니라, 그때까지 끝나지 않을 프로그램을 작성하는 것으로부터 벗어날 수 있는 통찰력을 주기에 중요한 것입니다.

  하노이의 탑의 경우, 수학적 모델은 간단합니다. 함수 T(n)을 재귀적으로 정의해보죠. T(n)은 하노이의 탑에서 n개의 원판을 다른 기둥으로 옮기는 데 필요한 이동 횟수입니다. 아마 다음과 같은 등식이 성립할 것입니다.

  이런 등식을 이산 수학에서는 재귀 관계(recurrence relation)라고 칭합니다. 재귀 관계는 재귀 프로그램의 연구에서 자연스럽게 발생합니다. 우리는 종종 이를 이용해서 닫힌 수식들을 유도해낼 수 있죠. T(n)의 경우, T(1)=1, T(2)=3, T(3)=7, T(4)=15, 즉 T(n)=2^n-1입니다. 재귀 관계는 이것이 사실임을 증명할 수 있는 방법을 제시합니다. 바로 점화식이죠.

  따라서 수학적 귀납법으로 인해 n>0인 모든 정수에 대해 성립하게 됩니다. 

  T(n)의 값을 알게 된다는 것은, 곧 모든 이동을 끝마치는데 걸리는 시간을 예상할 수 있다는 것입니다. 만약 수도승들이 원판을 초당 하나씩 옮길 수 있다면, 20개의 원판을 옮기는 데에는 1주일이, 30개의 원판을 옮기는 데에는 31년이, 40개의 원판을 옮기는 데에는 348세기가 걸리게 됩니다. 64개의 원판을 옮기려면, 1억 4천만 년이 걸립니다. 실제 수도승들은 이보다 더 오래 걸리겠죠. <프로그램 2.3.2>를 이용할 수 없으니 말입니다.

  컴퓨터들 역시 지수적 상승에는 상대가 되지 않습니다. 컴퓨터는 초당 억 단위의 연산을 해내지만, 2^1000을 계산할 때에는 수도승이나 컴퓨터나 별 다를 바 없겠죠. 여기서 얻는 교훈은 심오합니다. 여러분들은 재귀를 통해 지수적 시간을 소모하는 프로그램들을 아주 쉽게 작성해낼 수 있습니다. 따라서 거대한 n에서는 작동하지 않을 것이라는 사실입니다.

계속.