4강: 재귀 알고리즘(recursive algorithms)

재귀 알고리즘은 알고리리즘의 성질 중 하나. 주어진 문제가 있을 때, 이것을 같은 종류의 보다 쉬운 문제의 답을 이용해서 풀 수 있는 성질을 이용해서, 같은 알고리즘을 반복적으로 적용함으로써 풀어내는 방법.

예를 들면, 1부터 n까지 모든 자연수의 합을 구하는 문제 (sum(n))는, 1부터 n-1까지의 모든 자연수의 합을 구하는 문제 (sum(n - 1))를 풀고, 여기에 n을 더해서 그 답을 찾을 수 있음. 즉,
sum(n) = sum(n - 1) + n

위의 sum(n)을 구하는 문제를 재귀적으로 해결하기 위해서는, 그 종결 조건(trivial case)을 명시해야 한다. 위 수식이 자연수들의 합을 구하는 문제를 푸는데 적용될 수 있으려면, 무한히 n - 1 까지의 합을 적용해서는 안되고, 이에 대한 답을 주어야한다.

1부터 1까지의 모든 자연수들의 합은 1이므로, 위 점화식에 덧붙여 하나의 수식을 추가해야한다. sum(1) = 1

이 두 수식을 묶으면, 1부터 n까지의 자연수의 합을 구하는 문제의 답이 나온다. 이것이 재귀 알고리즘(recursive algorithm)이다.