[자료구조&알고리즘] 재귀 알고리즘(1)

※ 재귀 알고리즘(Recursive Algorithms)

- 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

예를 들어 1부터 n까지 모든 자연수의 합을 구하는 문제는 1부터 n-1 까지의 모든 자연수의 합을 구하고 거기에 n을 더하면 되므로 sum(n) = sum(n-1) + n 을 하면 된다.

 

위와 같이 sum(n) 을 구하는 문제를 재귀적으로 해결하기 위해선, 종결 조건(trivial case)를 명시해야 한다.

이를 수학에서는 '점화식'이라는 용어를 사용함. 1부터 1까지의 모든 자연수의 합은 1 이므로, 위 점화식에 하나의 수식을 추가해야 한다. sum(1) = 1. 이 수식을 묶으면 1부터 n까지의 자연수의 합을 구하는 문제의 답이 되는데 이를 재귀 알고리즘(recursive algorithm)이다.