  재귀로 1부터 n까지 합 리턴하기(설명) [1890 / 0762] 

Time Limit(Test case) : (ms)
Number of users who solved : 0   Total Tried : 0 
The Champion of this Problem (C++) : N/A 
My Best Submission (C++) : N/A

[koistudy.net (T. HS Jeon 2017)]


Background

*주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다.
------

한 정수 n을 입력받아 1부터 n까지의 정수 합을 출력하시오.
(단, 반복문은 사용할 수 없다.)


참고
1부터 n까지의 정수 합을 출력하는 문제에 대해서 하향식 재귀 설계 방법을 적용해 본다면,

1. f(n)을 1부터 n까지의 정수합 이라고 생각(정의)한다.

그러면,
f(k)는 1부터 k까지의 합을 의미하고,
1부터 k까지의 합을 출력하는 문제는,
1부터 (k-1)까지의 합을 이미 계산해 둔 상태에서 k만 더 더해 출력하는 문제로 바꾸어 
일반화 시킬 수 있고, 다음과 같은 점화 관계식으로 표현할 수 있다.

f(k) = f(k-1)+k

함수 호출 위치에 리턴하는 값이 정수 값이므로, 정수형(int, long long int) 함수로 설계해야 한다.


2. 1.에서 만든 명확한 정의와 큰 문제를 보다 작은 문제로 바꾸는 관계를 이용해 함수로 작성(설계)한다.

int f(int k) //1부터 k까지의 정수합은
{
  return f(k-1)+k; //1부터 (k-1)까지의 정수합에 k를 더 더하면 된다.
}

이렇게 큰 문제를 해결하기 위해,
보다 작은 문제를 해결한 결과를 이용하도록 만 작성하면 무한 재귀 호출 상태에서 빠져나오지 못하기 때문에
재귀 호출을 중단시키기 위한 중단 조건과 처리해야할 작업을 추가로 작성해 넣어야 한다.


3. 2.에서 만든 함수에 재귀 호출 중단 조건과 리턴해야 할 값을 추가한다.

가장 작은 문제인 1부터 1까지의 합은 1임을 알고 있으므로 
다음과 같은 재귀 호출 중단 조건을 추가할 수 있다.
(함수 호출 중단 시에는 이전 위치에 돌려다 놓는 값을 return 값; 으로 작성해야 한다.)

int f(int k) //1부터 k까지의 정수합은
{
  if(k <= 1) return 1; //1부터 1까지의 합은 1이다. 부등식을 사용하는 것이 안정적이다.
  return f(k-1)+k;
}
와 같이 어떤 상태까지만 재귀적으로 호출되는 재귀 함수를 완성시킬 수 있다.


위와 같은 생각과 함수 설계 과정을 통해,
1부터 k까지의 정수합을 구하는 예시코드는 다음과 같이 작성할 수 있다.

#include <stdio.h>

int n;

int f(int k)
{
  if(k <= 1) return 1;
  f(k-1);
  printf("*");
}

int main()
{
  scanf("%d", &n);
  printf("%d\n", f(n));
}
Input

int 형 정수(n) 1개가 입력된다.
(1 <= n <= 100)
Output

1 부터 n 까지의 정수 합을 출력한다.
IO Example

입력
10

출력
55