15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Recursion on arrays walks one index i through the array. When i equals the length, the unprocessed suffix is empty and the call returns directly. Otherwise it reads values[i] and combines it with the recursive call on i + 1. That makes n + 1 calls, so O(n) time and O(n) call-stack space.
| Index meaning | i is where the unprocessed suffix starts |
|---|---|
| Base case | i == length, the suffix is empty; check it before reading text[i] |
| Valid indices | 0 through length, inclusive |
| Calls for length n | n + 1 |
| Time and stack | O(n) time and O(n) call-stack space, no extra array or string |
The lesson assumes you can identify a base case and a recursive case, and that you have seen tail recursion: a recursive call that moves toward a stopping condition.
An array or string traversal can be described by one index:
i is the current position.i are no longer the current call's responsibility.i through the end still need work.For an array of length n, valid traversal indices are 0 through n, inclusive.
i < n, position i can be read.i == n, no position remains. This is the base case.0 or above n is outside this lesson's function contract.The bounds rule is:
Check whether
i == lengthbefore readingvalues[i]ortext[i].
Start with this call:
1sumFrom([2, 4, 1], 0)The array has length 3.
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Value | 2 | 4 | 1 |
At index 0, the function is responsible for the whole suffix:
1indices 0 through 2: 2 + 4 + 1It reads the current value, 2, then gives the remaining suffix to a smaller call:
12 + sumFrom(values, 1)The index is not an accumulator. It identifies where the unprocessed suffix begins.
Each recursive call makes one state change:
1i becomes i + 1The index i walks [2, 4, 1] from 0 to 3, each call deferring its addition. At i = 3 the suffix is empty and returns 0; the returns 1, 5, 7 unwind the sum.
Follow the calls downward first. Each call reads one valid position, then defers its addition until the smaller call returns.
| Call | Current index | Current value | Deferred expression |
|---|---|---|---|
sumFrom(values, 0) | 0 | 2 | 2 + sumFrom(values, 1) |
sumFrom(values, 1) | 1 | 4 | 4 + sumFrom(values, 2) |
sumFrom(values, 2) | 2 | 1 | 1 + sumFrom(values, 3) |
sumFrom(values, 3) | 3 | none | return 0 |
At index 3, the index equals the length. There is no values[3] to read. The remaining suffix is empty, and the sum of an empty suffix is 0.
Resolve the deferred additions while calls return:
| Returning call | Calculation | Return value |
|---|---|---|
sumFrom(values, 3) | base case | 0 |
sumFrom(values, 2) | 1 + 0 | 1 |
sumFrom(values, 1) | 4 + 1 | 5 |
sumFrom(values, 0) | 2 + 5 | 7 |
1sumFrom([2, 4, 1], 0) returns 7Strings use the same index advance. Instead of adding an array value, inspect whether the current character matches a target.
For:
1countFrom("banana", 0, 'a')the index moves from 0 to 6. It contributes 1 only at indices 1, 3, and 5, where the character is 'a'.
For the call sumFrom(values, 1), the function must sum only:
1values[1] through values[2]It must not include values[0]. The earlier call already read that value.
The following remains true at every valid call:
For every call
sumFrom(values, i)where0 <= i <= values.length, the function returns the sum of exactly the elements at indicesithroughvalues.length - 1. Elements beforeiare already excluded from that call's responsibility.
The traversal invariant states that the current index marks the first element that still belongs to the call.
For a string count:
1countFrom(text, i, target)counts target characters only from index i through the final string position. Characters before i are excluded.
Suppose sumFrom(values, i) is responsible for the suffix beginning at i.
There are two cases.
If i == values.length, the suffix is empty.
1return 0Check the base-case condition before indexing the array.
If i < values.length, read values[i].
The rest of the work is the sum of the suffix beginning at the next index:
1sumFrom(values, i + 1)Combine the current value with that result:
1values[i] + sumFrom(values, i + 1)Character counting follows the same structure:
i == text.length.text[i] matches target.1 for a match and 0 otherwise.i + 1.The one-position advance makes the unprocessed suffix shrink on every recursive call.
sumFromInput
values: an array of numbers.i: an integer in the inclusive range 0 through values.length.Return value
values[i] through values[values.length - 1].Mutation behavior
values.Boundary
i == values.length returns 0.0 or above values.length is rejected.1function sumFrom(values, i) -> number
21. if i < 0 or i > values.length
32. reject invalid index
43.
54. if i == values.length
65. return 0
76.
87. return values[i] + sumFrom(values, i + 1)The recursive call at line 7 has the same contract as the original function, but its index is one larger.
countFromInput
text: a string.i: an integer in the inclusive range 0 through text.length.target: one character.Return value
target in text[i] through text[text.length - 1].Mutation behavior
text.Boundary
i == text.length returns 0.0 or above text.length is rejected.1function countFrom(text, i, target) -> integer
21. if i < 0 or i > text.length
32. reject invalid index
43.
54. if i == text.length
65. return 0
76.
87. matchCount <- 0
98. if text[i] == target
109. matchCount <- 1
1110.
1211. return matchCount + countFrom(text, i + 1, target)matchCount is 1 exactly when the current character equals the target. It is 0 for every other character.
Dry-run sumFrom([2, 4, 1], 0) using the line numbers above.
Let values = [2, 4, 1], so values.length = 3.
| Call | Line 1 condition | Line 4 condition | Line 7 action |
|---|---|---|---|
sumFrom(values, 0) | false: 0 is valid | false: 0 != 3 | return values[0] + sumFrom(values, 1) → 2 + sumFrom(values, 1) |
sumFrom(values, 1) | false: 1 is valid | false: 1 != 3 | return values[1] + sumFrom(values, 2) → 4 + sumFrom(values, 2) |
sumFrom(values, 2) | false: 2 is valid | false: 2 != 3 | return values[2] + sumFrom(values, 3) → 1 + sumFrom(values, 3) |
sumFrom(values, 3) | false: 3 is valid | true: 3 == 3 | line 5 returns 0 |
No call reads an invalid index. The call with i = 3 stops at line 4 before line 7 could attempt values[3].
1sumFrom(values, 3) returns 0
2
3sumFrom(values, 2)
4= values[2] + sumFrom(values, 3)
5= 1 + 0
6= 1
7
8sumFrom(values, 1)
9= values[1] + sumFrom(values, 2)
10= 4 + 1
11= 5
12
13sumFrom(values, 0)
14= values[0] + sumFrom(values, 1)
15= 2 + 5
16= 7The final returned value is:
17We prove correctness from the structure of the suffix.
sumFromFor every valid index i, sumFrom(values, i) must return the sum of the suffix from i through the final index.
Base case.
When i == values.length, no array elements remain. The required suffix is empty. The function returns 0, which is the sum of that empty suffix.
Recursive case.
Assume i < values.length and assume the smaller call:
1sumFrom(values, i + 1)returns the sum of exactly the elements from index i + 1 through the end.
The current call reads values[i], then returns:
1values[i] + sumFrom(values, i + 1)By the assumption, the second part sums every remaining element after i. Adding values[i] produces the sum of exactly the elements from i through the end.
Termination.
Each recursive call changes i to i + 1. Starting from a valid index at or below values.length, the index eventually reaches values.length. At that point, the base case returns. Therefore, the recursion terminates.
sumFrom(values, i) satisfies its contract for every valid i.
countFromBase case.
When i == text.length, the remaining suffix is empty. It contains zero occurrences of target, and the function returns 0.
Recursive case.
At a valid position i, matchCount is set to 1 exactly when text[i] == target; otherwise it remains 0. The recursive call counts target occurrences in the remaining suffix beginning at i + 1. Their sum counts the target at the current character, if present, plus all target characters after it.
Termination.
The index increases by one each time and eventually equals text.length, which reaches the base case.
Consider an array of length n and the call:
1sumFrom(values, 0)There is one call for each index from 0 through n - 1, plus one boundary call at index n.
1n + 1 callsEach non-base call performs:
Each operation is O(1). The boundary call also performs constant work.
The total work is proportional to n, so time is:
1O(n)The calls remain active while deeper calls run. The deepest active sequence has one frame per traversed index, plus the boundary frame. That is proportional to n.
Auxiliary call-stack space is:
1O(n)Neither function creates another array or string proportional to the input length. Apart from the recursion stack and a constant number of local values, it uses no additional collection-sized storage.
countFrom has the same call pattern and the same O(n) time and O(n) auxiliary call-stack space.
Incorrect assumption
1if i == values.length - 1
2 return 0Smallest exposing input
1sumFrom([5], 0)Here, values.length - 1 is 0, so the function stops immediately.
Wrong result
10The value 5 was never included.
Correction
Stop when i == values.length, not when i reaches the final valid index.
1if i == values.length
2 return 0The final valid index must still be processed.
Incorrect ordering
1current <- values[i]
2if i == values.length
3 return 0Smallest exposing input
1sumFrom([], 0)The length is 0, so index 0 is the boundary, not a readable position.
Wrong result
1bounds errorThe code attempts to read values[0] from an empty array.
Correction
Check the base case first.
1if i == values.length
2 return 0
3
4current <- values[i]Incorrect recursive call
1return values[i] + sumFrom(values, i)Smallest exposing input
1sumFrom([2], 0)The call at index 0 repeatedly creates another call at index 0.
Wrong result
1nonterminationThe index never reaches the boundary.
Correction
Advance by one position.
1return values[i] + sumFrom(values, i + 1)Incorrect counting line
1matchCount <- 1The incorrect line adds one regardless of whether the current character equals the target.
Smallest exposing input
1countFrom("aba", 0, 'a')Wrong result
13There are only two 'a' characters.
Correction
Add one only when the current character equals the target.
1matchCount <- 0
2if text[i] == target
3 matchCount <- 1These valid calls show the intended boundary behavior:
| Call | Result |
|---|---|
sumFrom([], 0) | 0 |
sumFrom([5], 0) | 5 |
sumFrom([2, 4, 1], 3) | 0 |
countFrom("", 0, 'a') | 0 |
countFrom("banana", 0, 'a') | 3 |
Calls such as sumFrom([2, 4, 1], -1) or countFrom("banana", 7, 'a') are outside the stated contract and must be rejected or handled by a documented policy.
Implement these two functions:
1sumFrom(values, i)
2countFrom(text, i, target)The executable tests verify this contract:
1sumFrom([], 0) == 0
2sumFrom([2, 4, 1], 0) == 7
3sumFrom([2, 4, 1], 2) == 1
4countFrom("banana", 0, "a") == 3
5countFrom("", 0, "a") == 0Your functions must check the boundary before indexing, advance from i to i + 1, preserve the unprocessed-suffix responsibility, and count a character only when it equals the target.
1def sum_from(values, i):
2 if i == len(values):
3 return 0 # empty suffix, checked before indexing
4 return values[i] + sum_from(values, i + 1)
5
6def count_from(text, i, target):
7 if i == len(text):
8 return 0
9 match_count = 1 if text[i] == target else 0
10 return match_count + count_from(text, i + 1, target)
11
12print(sum_from([2, 4, 1], 0), count_from("banana", 0, "a"), sum_from([], 0), sum_from([5], 0))1public class Main {
2 static int sumFrom(int[] values, int i) {
3 if (i == values.length) return 0; // empty suffix, checked before indexing
4 return values[i] + sumFrom(values, i + 1);
5 }
6
7 static int countFrom(String text, int i, char target) {
8 if (i == text.length()) return 0;
9 int matchCount = text.charAt(i) == target ? 1 : 0;
10 return matchCount + countFrom(text, i + 1, target);
11 }
12
13 public static void main(String[] args) {
14 System.out.println(sumFrom(new int[]{2, 4, 1}, 0) + " " + countFrom("banana", 0, 'a')
15 + " " + sumFrom(new int[]{}, 0) + " " + sumFrom(new int[]{5}, 0));
16 }
17}1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6int sumFrom(const vector<int>& values, int i) {
7 if (i == (int)values.size()) return 0; // empty suffix, checked before indexing
8 return values[i] + sumFrom(values, i + 1);
9}
10
11int countFrom(const string& text, int i, char target) {
12 if (i == (int)text.size()) return 0;
13 int matchCount = text[i] == target ? 1 : 0;
14 return matchCount + countFrom(text, i + 1, target);
15}
16
17int main() {
18 cout << sumFrom({2, 4, 1}, 0) << " " << countFrom("banana", 0, 'a') << " "
19 << sumFrom({}, 0) << " " << sumFrom({5}, 0) << endl;
20}1function sumFrom(values, i) {
2 if (i === values.length) return 0; // empty suffix, checked before indexing
3 return values[i] + sumFrom(values, i + 1);
4}
5
6function countFrom(text, i, target) {
7 if (i === text.length) return 0;
8 const matchCount = text[i] === target ? 1 : 0;
9 return matchCount + countFrom(text, i + 1, target);
10}
11
12console.log([sumFrom([2, 4, 1], 0), countFrom('banana', 0, 'a'), sumFrom([], 0), sumFrom([5], 0)].join(' '));Return 0 when i equals the length, otherwise return values[i] + sumFrom(values, i + 1). For [2, 4, 1] the calls return 0, then 1, then 5, then 7. The index marks where the unprocessed suffix begins.
Use the same walk. At i == length return 0. Otherwise add 1 when text[i] equals the target and 0 when it does not, then add the call on i + 1. For banana and 'a' the matches are at indices 1, 3 and 5, so the answer is 3.
At i == length there is no element to read. Reading values[i] first fails on an empty array, because index 0 is already the boundary. Test the base case, then read.
No. That stops one element early, and sumFrom([5], 0) returns 0 instead of 5. Stop at i == length, so the last valid index is still processed.
The time is the same O(n), but recursion adds n + 1 stack frames where a loop needs O(1) extra space. For long inputs the loop is safer, because the stack depth is limited by the runtime.