Sum of N Numbers Using Recursion
Solve this ProblemEasy10 min
Topics
BasicsRecursion
Companies
TCSInfosysWipro
Given
n, return 1 + 2 + … + n — computed with recursion rather than a loop or a formula.
RecursionRecursionA function solving a problem by calling itself on a smaller version of the same problem. expresses the sum as "n plus the sum of the smaller problem", and needs a base caseBase CaseThe input for which a recursive function returns directly without calling itself, so the recursion stops. so the calls eventually stop. Every waiting call occupies a frame on the call stackCall StackThe memory area that holds one frame per active function call, in last-in, first-out order., so the shape of the recursion decides how deep that stack grows: n levels for the plain version, about log n when the range is split in half.
Test Case 1:
Input:n = 5
Output:15
Explanation:5 + 4 + 3 + 2 + 1 = 15, computed as 5 + sum(4), 4 + sum(3), … down to sum(0) = 0.
Test Case 2:
Input:n = 0
Output:0
Explanation:The base case: nothing to add.
Constraints
- ◆
0 ≤ n ≤ 500
Try the Dry Run
Approach & Solutions
Plain RecursionGood
The sum of 1..n is n plus the sum of 1..(n − 1). Write exactly that: sumToN(n) returns n + sumToN(n − 1). A recursive function also needs a base case that stops the calls — the sum of no numbers, sumToN(0), is 0. Each call waits on the call stack until the one below it returns.
Time
O(n)Space
O(n) call stackJava
class Solution {
public int sumToN(int n) {
if (n == 0) {
return 0;
}
return n + sumToN(n - 1);
}
}Split the Range in HalfOptimal
Generalise to rangeSum(lo, hi), the sum of lo..hi. Split the range at its midpoint and add the sums of the two halves, with base cases for an empty range (0) and a single number (itself). The work is still O(n), but each call halves the range, so the call stack is only about log₂ n deep instead of n deep.
Time
O(n)Space
O(log n) call stackJava
class Solution {
int rangeSum(int lo, int hi) {
if (lo > hi) {
return 0;
}
if (lo == hi) {
return lo;
}
int mid = (lo + hi) / 2;
return rangeSum(lo, mid) + rangeSum(mid + 1, hi);
}
public int sumToN(int n) {
return rangeSum(1, n);
}
}