어딜 뒤져봐도 제일 많이 나오는 예시일 것이다. 그래서 선택했다. 재귀 호출을 이용하여 1부터 n까지의 합을 구하는 함수를 작성해보자. 우선 sum(n)이라 하고, 다음과 같이 정의한다.
sum(n) = n + (n-1) + …… + 3 + 2 + 1
이걸 어떻게 재귀초 풀어야 하나를 생각해보면 바로 바로 생각은 안 날 것이다. 그래서 알고리즘 수업에서 이용하는 방법 중 하나인 작은 범위 안에서 무식하게 해보는 방법대로 해보자. 일단 5까지의 합을 생각해보자.
sum(5) = 5 + 4 + 3 + 2 + 1
이렇게 보면, 앞에 5를 제외한 나머지의 합의 경우에는 sum(4)와 같은 구조이다. sum(4)가 1+2+3+4이기 때문이다. 그걸 보면 다음과 같이 할 수 있다.
sum(5) = 5 + sum(4)
이 방법대로 쭉 내려가서 식을 작성해보면 다음과 같이 된다.
sum(5) = 5 + sum(4)
sum(5) = 5 + 4 + sum(3)
sum(5) = 5 + 4 + 3 + sum(2)
sum(5) = 5 + 4 + 3 + 2 + sum(1)
sum(5) = 5 + 4 + 3 + 2 + 1
이렇게 보면, sum(n)은 다음과 같은 구조라고 알 수 있다.
sum(n) = n + sum(n-1)
그러나, 이렇게만 하면 재귀가 종료가 되질 않는다. 음수 아래로 계속 끊기지 않고 연산할 수 있기 때문이다. 그렇기 때문에 이 재귀가 종료될 수 있는 조건을 제시해 줘야 한다. 여기에서는 1을 대입하게 되면 그대로 합이 1이 된다. 이걸 정의하면 1이 되었을 때 1을 할당하고 종료시킬 수 있게 된다. 이 내용을 하나의 내용으로 정리하면 아래와 같다.
- sum(n)
- 1, n=1
- n + sum(n-1), n > 1
이를 C 함수로 나타내게 되면, n=1이면 1을 반환하고, 그렇지 않으면 n+sum(n-1)을 반환하도록 한다. 조건식으로 충분히 나눌 수 있고, 조건식 처리로 재귀 종료를 확인할 수 있는 것이다.
int sum(int n)
{
if(n==1)
return 1;
else
return n+sum(n-1);
}
이 함수를 이용한 예제가 아래의 예시이다.
