이번에는 재귀 알고리즘을 살펴봅시다.
재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용하여 해결하는 것을 말합니다. 수학에서 특정 명제가 참인지 증명하기 위해 명제를 이용하여 증명하는 방법과 같은 방식입니다. 예를 들어 “n!을 f(n)이라 할 때 n>1인 정수이면 n!은 n*f(n-1)이다.”라는 명제를 증명하면 다음과 같이 증명할 수 있습니다.
n-1일 때 위 명제가 참이라 가정하자. 가정에 의해 f(n-1) = (n-1)*(n-2)*…*3*2*1 이다.
n*f(n-1) = n*(n-1)*(n-2)*…*3*2*1 = n! 이므로 위 명제는 참인 명제이다.
이처럼 자신을 이용하여 문제를 해결하는 방법을 재귀적 귀납법이라 하는데 이와 같은 방법으로 문제를 해결하는 알고리즘을 재귀 알고리즘이라 부릅니다.