6. 재귀 알고리즘

언휴) 재귀적인 방법으로 문제를 해결하는 알고리즘은 탈출 조건에 주의해야 해. 학생) 탈출할 수 있다는 것을 증명해야 한다는 것이죠.

이번에는 재귀 알고리즘을 살펴봅시다.

재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용해서 해결하는 알고리즘입니다. 수학에서 명제가 참인지 거짓인지 증명하기 위해 명제를 이용해서 증명하는 방법과 같은 방식입니다.

예를 들어 “n! 을 f(n)이라고 할 때 f(1)=1이고 n>1인 정수이면 f(n)=n*f(n-1)이다.”라는 명제를 증명하면 다음처럼 증명할 수 있습니다.

n-1일 때 위 명제가 참이라고 가정합시다.

가정에 의해 f(n-1) = (n-1)*(n-2)*(n-3)*…*3*2*1입니다.

f(n) = n*(n-1)*(n-2)*(n-3)*…*3*2*1 = n*f(n-1) 이므로 위 명제는 참인 명제입니다.

이처럼 명제 자신을 이용하여 명제를 증명하는 것을 재귀적 귀납법이라고 부르는데 이러한 방법으로 문제를 해결하는 알고리즘을 재귀 알고리즘이라고 부릅니다.

재귀 알고리즘으로 문제를 해결할 때 주의할 점은 탈출 조건입니다. 재귀 알고리즘으로 문제를 해결할 때는 재귀 호출을 수행하기 이전보다 탈출 조건에 근접하다는 것을 증명할 수 있어야 합니다. 만약 이를 증명하지 못하면 영원히 문제를 해결하지 못할 수 있습니다.

“재귀 알고리즘으로 문제를 해결할 때 주의할 점은 탈출 조건입니다.”

예를 들어 n!를 구하는 알고리즘을 f(n)이라고 할 때 n이 0 이하일 때는 오류를 반환하고 1일 때는 1을 반환하게 해야 합니다. 이와 같이 하면 재귀 호출하기 전보다 n 값이 1이 줄어들어 탈출 조건에 근접합니다. 만약 탈출 조건을 작성하지 않으면 무한 재귀로 스택 오버 플로우가 발생합니다. 

Factorial(n)

    조건 n<=0    오류

    조건 n IsEqual 1   1 반환

    반환 n * Factorial(n-1)

이를 코드로 표현하면 다음과 같습니다.

▷ 실행 결과