691. Sum of First N Natural Numbers

Given a positive integer N, return the sum of the first N natural numbers (1 + 2 + 3 + ... + N) using recursion. The function must be recursive — you may not use the formula N*(N+1)/2 directly without a recursive call chain.

Input: A single positive integer N (1 ≤ N ≤ 100000).

Output: A single integer — the sum 1 + 2 + ... + N.

Examples

Input: 5
Output: 15
Explanation: 1+2+3+4+5 = 15. Recursion: sum(5)=5+sum(4)=5+10=15.

Input: 1
Output: 1
Explanation: Base case: sum(1)=1.

Input: 100
Output: 5050
Explanation: Classic Gauss sum: 100×101/2 = 5050.

Constraints

• 1 <= N <= 100000

Asked by