[재귀]04. 재귀함수 디자인 절차

앞선 포스트에서 기본적인 재귀의 특성과 재귀가 반드시 정복해야할 산임을 배웠다. 하지만 재귀 함수의 동작을 이해하더라도 재귀 함수를 작성하기가 쉽지는 않다. 

이번 포스트에서는 어떻게 재귀 함수를 디자인 해야할지 살펴보고 연습해보자.

 

재귀 함수 디자인

 

재귀 함수 디자인 절차

재귀함수는 수학적 귀납법을 이용한 점화식을 찾아서 문제를 해결한다. 수학적 귀납법은 크게 다음의 두 가지 사실을 증명하는 것이다.

1. n=1일 때, 명제 p(n)이 성립한다.
2. n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때도 명제 p(n)이 성립한다.

 

재귀함수를 작성할 때도 수학적 귀납법에 의거해서 작성해주는데 먼저 구하려는 내용을 수학적 귀납법으로 풀고 점화식을 찾아야 한다.풀이 결과 1번 항목이 base part가 되고 2번 항목이 inductive part가 된다. 그런데 함수를 작성할 때는 2번을 먼저 작성한 후에 1번을 작성하는 것이 좀 더 편하다.

 

수학적 귀납법으로 식을 풀었다면 이를 바탕으로 재귀 함수를 디자인 할 때는 다음의 과정을 따라보자.

1. 함수의 역할을 명확하게 정의한다. 이때 문제의 크기를 결정하는 결정 요인이 무엇인지 찾는다.
2. 수학적 귀납법 2단계에 해당하는 inductive part 부분을 작성한다. 작은 입력(이전 재귀 단계)에서 제대로 동작한다고 가정하고  현재 메서드에서 진행할 일들만 flat하게 작성한 후 더 큰 입력(다음 재귀 단계)를 호출한다. 이때 주의할 점은 inductive part에서는 해당 메서드에서 현재 자기가 할 일만 처리해야지 다음 상황, 이전 상황까지 고려하지 않는다. 이전 사항은 이전에서 잘 처리되었기 때문에 내가 호출되었고 다음 사항은 다음에서 알아서 한다는 믿음을 갖자.
3. 수학적 귀납법 1단계를 이용해서 탈출 조건인 base part를 작성한다. 자명한 기저조건을 이용하여 언제나 return 될 수 있는 경우를 구성해야 한다.

앞에 인형이 잘 만들어졌으니까 내 차례가 왔겠지? 나도 잘 만들어서 다음으로 넘겨주자!

처음에는 재귀 함수 작성이 상당히 어렵다. 이런 경우는 먼저 반복문을 작성해두고 재귀로 변경해보는 연습을 하자.

 

 

재귀함수 작성 연습

 

정수 N에서 M까지의 곱의 결과를 반환하시오.

위 요구사항을 수학적 귀납법으로 풀이해보면 아래와 같다.

수학적 귀납법 풀이
 - n=m 이면 m은 자명한 사실이다.
 - n =2, m=5인 상태에서 m을 고정하고 n을 변경시키며 식을 완성하면
 - f(2, 5) = 2 * f(3, 5)
            = 2 * 3 * f(4, 5)
            = 2 * 3 * 4 * f(5, 5)
            = 2 * 3 * 4 * 5 (∵ n=m이면 m이므로)

 - 일반화 f(n, m) = n * f(n+1, m)

 

이제 위의 풀이를 재귀로 표현해보자.

1. 함수의 역할 정의 및 결정 요인 설정
   - n부터 m 까지의 곱을 반환하는 함수 이며 결정요인은 n (n이 m까지 변한다.), m은 고정된 비결정 요인
   - getMulti(n, m)
2. inductive part 작성
   - getMulti(2, 5) = 2 * getMulti(3, 5) = 2 * 3 * getMuulti(4, 5)
   - 일반화: getMulti(n, m) = n * getMulti(n+1, m);
3. base part 작성
   - n=m인 경우 자신을 반환하고 종료

 

// 1. 함수 정의: n부터 m까지의 곱을 리턴하는 함수, n은 결정요인, m은 비결정 요인
static int getMulti(int n, int m) {
  // 3. base part: n==m이면 m을 반환하고 종료
  if (n == m) {
    return m;
  }
  // 2. inductive part: 점화식 이용
  return n * getMulti(n+1, m);
}

 

함수가 잘 작성 되었다면 손컴파일해서 메모리에서 메서드의 동작도 살펴보자.

 

 

연습만이 살길!!

다음의 예들에 대해서 위 절차대로 재귀 함수로 작성해보자.

1. n^m의 결과를 반환하시오. (2^5 => 32)
2. 전달되는 10진수의 각 자리수의 합을 출력하시오. (12345 => 15)
3. 10진수 10을 2진수 문자열로 반환해보자. (10진수 10 -> 0b1010)
4. 파라미터로 전달된 크기가 n인 int [] arr에서 최대값을 찾아서 반환하시오.({10, 8,5,7,19,6,1} => 19)
5. 주어진 문자열이 palindrome인지 판단하시오.(소주주소, 소주만병만주소는 palindrome)
6. 주어진 2차원 배열을 사각형 형태로 출력해보자.(int[][] arr2 = { { 11, 12, 13 }, { 20, 30, 40 } };)