재귀호출 방식의 문제해결 - 1

1. 재귀호출의 상징적인 의미

 재귀호출을 통한 문제해결은 수학적 귀납법과 유사한 모습을 보입니다.

수학적 귀납법의 원리는 만약 자연수에 대한 어떤 성질 P가 두 조건

     • P(0)은 참이다.

     • P(n)이 참이면 항상 P(n + 1)도 참이다.

을 만족하면, P(n)은 모든 자연수 n에 대해 성립한다는 것입니다.

재귀호출의 과정은 이 귀납법을 반대로 적용한 것입니다.

P(n-1) 이 참이기 때문에 P(n) 이 참이다.

P(n-2) 가 참이었기 때문에 P(n-1) 이 참이다.

종래에는 P(0) 가 참이었음을 증명하므로 재귀호출을 통한 문제해결이 가능합니다.

주어진 문제를 그보다 작은 문제로 환원하는 것이 재귀(Recursion) 입니다.

재귀는 문제의 크기를 줄여나감으로써 결국 해결 가능한 최소의 크기로 만들어 문제를 해결하는

방법입니다. 이처럼 큰 문제를 보다 작은 문제로 환원하여 해결해 나가는 접근 방식을

분할 정복(Divide and Conquer) 전략이라고 부릅니다.

여기서 재귀의 문제해결 방식이 주목하는 부분은 큰 문제건 작은 문제건 그 본질은 같다

라는 것입니다. 문제의 크기만 달라졌지 그 성격은 완전히 동일하다는 것이지요.

따라서 재귀호출은 어떤 함수가 실행하는 도중에 자기 자신을 호출하는 것을 말합니다.

자기 자신을 다시 호출하는 이유가 큰 문제건 작아진 문제건 문제의 스타일이 동일하다는 것입니다.

이렇게 재귀가 진행되고, 문제의 크기가 직접 해결할 수 있을 정도로 작아졌을 때를

베이스 케이스(Base Case) 또는 디제너릿 케이스(Degenerate Case) 라고 합니다.

2. 재귀적 팩토리얼

자연수 n 에 대해서 n!( n 팩토리얼 ) 은 다음과 같이 정의됩니다.

     

숫자 n 이 주어졌을 때 n!을 구하는 문제를 생각해 봅시다. 우리는 이것을 단순한 반복문의 형태로

구현할 수 있어 보입니다.

int Factorial(int n) {     int iRet = 1;     for (int i = 0; i < n; ++i)     {         iRet *= (i+1);     }     return iRet; }

위 코드는 1부터 주어진 n 까지 누적해서 곱한 값을, 반복문을 통해서 iRet 이라는 변수에

저장하고 있습니다.

이렇게 반복문을 통해서 문제를 해결하게 되면, 팩토리얼의 수학적 정의가 어떻게 구현되어있는지

빠르게 판단이 어렵습니다. 반면이 이 문제를 재귀호출로 구현해보도록 하겠습니다.

int Factorial(int n) {     if (n == 1)         return 1;     else         return (n * Factorial(n - 1)); }

위 코드는 n 의 문제의 크기를 n-1 로 줄여서 다시 자기자신을 호출합니다.

해결할 수 있을 정도로 작아진 경우( n == 1) 에 1을 반환합니다.

이렇게 연쇄적 반환이 이루어지면서 이전에 호출했던 곳에서 현재 반환한 숫자보다 1 더 큰 숫자를

곱해주고 반환하게 됩니다.

즉 팩토리얼의 수학적 표현을 그대로 코드에 옮겨놓은 모양을 띄고 있습니다.

==> 다음 글로 이어집니다~~

- by Raimondo

게임 프로그래머 취업 전문 프로그래밍 학원 어소트락 평생교육원