PPractick

The problem

A fitness app awards points on a rising scale: 1 point on day 1, 2 on day 2, and so on, and it needs the total after N days, which is 1 + 2 + ... + N. There's a famous formula for it, but the exercise is to compute it recursively in two styles: parameterised recursion, where a running sum is carried along as an argument, and functional recursion, where each call returns its answer built from the smaller call's answer. The difference between "carry the result down" and "build the result on the way back up" is the core idea behind every recursive DP later on.

Example: N = 5 → 1 + 2 + 3 + 4 + 5 = 15.

Function signature

long long sumParameterised(int n, long long acc = 0);  // carries the running sum
long long sumFunctional(int n);                        // returns n + sum(n - 1)

Test cases

Input n	Output	Explanation
5	15	1 + 2 + 3 + 4 + 5
1	1
0	0	Empty sum
100	5050	Matches n(n + 1) / 2
10000	50005000	10,000 levels of recursion; fine for the default stack

(Confirm: 0 ≤ n ≤ 10^4 so the recursion depth is safe; the result can also be checked against n(n + 1) / 2.)

How interviewers phrase it

• "Find the sum of the first N natural numbers using recursion."
• "What's the difference between parameterised and functional recursion?"
• A lead-in to recursive factorial, array sum and, later, recursive DP.

Clarifying questions to ask

1. Must it be recursive, or is the formula acceptable?
2. How large can N be? (Recursion depth and overflow.)
3. Can N be 0?

Follow-ups to expect

1. "Parameterised vs functional?"
2. "Which one is tail recursive?"
3. "Can you do it in O(1)?"
4. "Why long long?"
5. "Complexity of the recursive versions?"

Related questions

• Factorial of a given number Easy
• Understand recursion by print something N times Easy
• Print name N times using recursion Easy
• Print 1 to N using Recursion Easy
• Print N to 1 using Recursion Easy
• Reverse an array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in