재귀함수 1부터 n까지 합 구하기

문제링크 : http://codeup.kr/JudgeOnline/problem.php?id=1905

해결방법 :

정수 n이 입력으로 들어오면 1부터 n까지의 합을 재귀함수로 구현해야한다.

따라서 재귀함수를 구현하기 위해 다음을 설계해야한다.

1.기저조건

2.재귀처리구문 

기저조건은 입력 n이 1이하인 것이고 그때는 n을 리턴한다.

재귀처리는 n(현재 숫자) + f(n-1) (하나 전의 숫자까지의 1부터 총합) 을 하면 우리가 구하고자하는 1부터 n까지의 합을 구할 수 있다.

여기서 재귀함수인 f(n-1)은 우리가 원하는 값을 리턴해준다는 것을 가정해두고 설계한다. (실제 직접따라 들어가보면 값을 구해준다. 신기신기)

이렇게 가정하고 설계해도 답을 구하는 것은 귀납적인 식으로 설정해두었기 때문에 오류가 안나는 것이다.

그 이유는 기저조건을 세웠고(처음오는 자연수에 대한 증명), f(n-1)과 f(n)은 같은 방식(n이만족되면 n+1도 맨족..)으로 구해나가기 때문에 귀납적 증명을 한 것과 동일하기때문이다. 

다음 수학 귀납법 설명 참조

모든 자연수가 어떤 성질을 만족시킨다는 명제에 대한 수학적 귀납법을 통한 증명은 다음과 같은 두 단계로 구성된다.

1. 처음 오는 자연수(0 또는 1)에 대한 증명
2. $${\displaystyle n}이 만족시킨다는 가정 아래, $${\displaystyle n+1}에 대한 증명

소스코드)

#include<iostream>
using namespace std;
int sumFromN(int n)
{ //1부터 n까지 총합을 리턴하는 함수
   if(n<=1)
       return n;
   else
     return n+sumFromN(n-1); 
}
 
int main()
{
  int n;
  cin >> n;
  printf("%d\n", sumFromN(n));
  return 0;
}