1부터 N까지 합을 구하고자 한다.
재귀적방법을 통해 작성하는 방법을 만드세요
재귀(Recursion)는 원래의 자리로 되돌아가거나 되돌아옴을 뜻한다.
재귀의 특성은 여러 가지 반복이나 특별히 반복되는 패턴들을 만들어 내는 특성을 가지고 있으며,
프랙탈 구조도 이러한 특성을 가지고 있다.
이를 바탕으로 프로그래밍 언어에서는 재귀함수를 만들 수 있다.
재귀함수에서 재귀적 정의가 필요하다. 이는 보통 재귀적 관계를 정의를 해야 한다.
예를 들어 함수 1~n까지의 합을 구하는 함수를 재귀적 관계를 이용해 정의해 보자
f(n)을 1~n까지의 합을 구하는 함수라고 정의하자.
여기서 f(n)을 재귀적으로 정의하기 위해서 f(n-1)을 이미 안다고 가정하면 함수 f(n)은 다음과 같이 정의 할 수 있다.
이와 같이 재귀적 관계는 수학의 증명 방법 중 하나인 수학적 귀납법으로 증명할 수 있다.
수학적 귀납법으로 증명하면
초항인 1일 때 f(1)=1 성립한다.
n-1일 때 f(n-1)이 된다.
임의의 n에 대해서 f(n-1)을 알고 있으므로 f(n)=f(n-1)+n로 구할 수 있다.
위와 같이 재귀적 정의로 구성된 식을 수학에서는 점화식이라고 한다.
이러한 점화식을 만들 수 있다면 이를 바로 재귀함수로 작성 할 수 있다.
수학에서의 점화식은 수를 기반으로 구성된다.
하지만 정보과학에서는 수뿐만 아니라 모양, 이미지 등의 모든 객체에 대해서 점화식으로 표현할 수 있다.
위의 점화식을 바탕으로 코드로 구현하면 다음과 같다.
f(n)이라는 함수는 반환값이 자연수이다.
int f(int n){
if(n==1) return 1;
else return f(n-1) +n;
}