Recursion on arrays and strings

Why it matters

Most recursion in interviews works on a sequence: an array of numbers, or a string of characters. Sorting, searching, checking a palindrome, reversing a word and finding the largest value all have a recursive form. Once you can write those, the backtracking in the next lessons becomes a small step. The key skill is the same in every case. You describe what is left to handle, and you pass that description into the next call.

The idea: pass a position, not a piece

Suppose you have a list of 10 numbers and you want the sum. One way is to take the first number, then ask for the sum of the other nine. That is a clean idea, and it is recursive. The problem is the word "other nine." In C++ a function that receives an array cannot cheaply produce a smaller array. Copying nine numbers costs time, and copying again for each call costs even more.

The fix is to pass a position instead. Think of reading a long book with a bookmark. The bookmark marks where you are. You handle the page at the bookmark, then you move the bookmark forward and keep going. You never tear out the pages you have finished. You just track where the unread part starts.

A recursive function does the same. It receives the whole array, which it never copies, and an index that marks where the unhandled part begins. The function handles the element at the index, then calls itself with the index moved on. When the index passes the end, there is nothing left and the function returns its base answer.

Two shapes cover almost every array or string problem in this lesson.

• One index moving forward. The function is f(arr, i). It handles arr[i], then calls f(arr, i + 1). The base case is i == n, which means the index has passed the last element. Sums, maximums and "is sorted" checks use this shape.
• Two ends moving inward. The function is f(s, lo, hi). It compares or swaps the elements at both ends, then calls f(s, lo + 1, hi - 1). The base case is lo >= hi, which means the two ends have met or crossed. Palindromes and reversals use this shape.

There is also a third shape, where the index moves through a sorted array by halving the range. Binary search is the famous example, and you will see it later in this lesson. It is the same idea with the range cut in half each time, not just moved by one.

Passing by reference and by value

C++ has two ways to pass an array to a function, and the difference matters a lot in recursion.

By value means the function gets its own copy. If you write int sumFrom(vector<int> a, int i), every call copies the whole vector. A vector of 1,000 numbers copied 1,000 times costs about a million element copies. The algorithm is O(n) in its logic, but the copying makes it O(n squared) in time.

By reference means the function gets a name for the original object, not a copy. Write const vector<int>& a to pass by reference and promise not to change the array. The & means reference. The const means read only. With this form, each call costs only the bytes needed to pass the reference, which is tiny.

Use const references for read-only input in recursion. Use a plain reference, vector<int>& a, when the function must change the array, as in the in-place reversal later in the lesson. For strings the same rule applies: const string& s for reading, string& s for changing.

A short look at what happens inside. A reference is internally a pointer, which is the address of the original object. Passing it copies only the address, usually 8 bytes on a 64-bit system. The function reads the elements through that address. No element is copied.

Worked example 1: sum, maximum and palindrome

Here are three functions that all use the one-index or two-ends shapes. Read the code once, then run it.

No input is needed. The output is:

21
9
1
0

Trace sumFrom(a, 0). It returns a[0] plus sumFrom(a, 1). That returns a[1] plus sumFrom(a, 2), and so on. At index 4, which equals the size of the vector, the base case returns 0. The answers climb back up: 0 + 7 is 7, then 2 + 7 is 9, then 9 + 9 is 18, and finally 3 + 18 is 21. The sum of the vector is 3 + 9 + 2 + 7, which is 21, as printed.

Trace maxFrom(a, 0). Its base case is different. It stops at the last index, not past it. At the last index it returns that element, which is the only candidate left. Going up, each call takes the larger of its own element and the maximum from the right. The result is 9.

The choice of base case matters. sumFrom stops when the index equals the size, so the function handles the empty tail. maxFrom stops at size minus one, because an empty range has no maximum at all. If you called maxFrom on an empty vector, a.size() - 1 would be -1, the check would never match, and the program would read past the vector. Always decide what the function returns for an empty input before you write the base case.

The palindrome check isPal uses two ends. It compares the characters at lo and hi. If they differ, the answer is false at once. If they match, it moves both ends inward. The base case lo >= hi means there is nothing left to compare. For "level", the calls go (0, 4), (1, 3), (2, 2), and at (2, 2) the base case returns true. The string "lever" fails at the first comparison, because "l" is not "r".

Now look at the two-ends picture with the visualizer. The two pointers close in on each other, which is exactly what the recursion does with lo and hi.

Step through the animation above, then compare it with the trace. Notice that each step looks at one pair. The palindrome check stops at the first mismatch, which is faster than checking every pair.

Two indexes moving toward the middle of the word level, comparing one pair per call

Worked example 2: reverse a string in place, and check for sorted order

The next example changes data, not just reads it. reverseStr swaps the two ends of a string, then recurses on the inside. The swap is the work done on the way down. Because the recursion has nothing to combine on the way up, the function returns void.

isSorted checks that each value is no bigger than the one after it. It returns false at the first problem and true at the end. It is one-index, but it compares each element with its neighbor instead of adding.

No input is needed. The output is:

egrof
1
0

Trace reverseStr on "forge", which has five characters at indexes 0 to 4. The string starts as f, o, r, g, e. The first call swaps index 0 and index 4, which gives e, o, r, g, f. The call then recurses with lo equal to 1 and hi equal to 3. It swaps index 1 and index 3, which holds o and g, so the string becomes e, g, r, o, f. Now lo equals 2 and hi equals 2, so the base case stops. The string reads "egrof". The middle letter r never moves, which is correct for an odd length.

The reference to the call is the key point. Each call handles one pair, and the pairs get closer to the middle. The function never needs to know the length of the whole string after the first call, because it has lo and hi.

Trace isSorted({1, 2, 2, 5}, 0). The check at index 0 is 1 against 2, which is fine, so the call moves to index 1. The check is 2 against 2, which is fine, so it moves to index 2. The check is 2 against 5, which is fine, and index 3 is the last index, so the base case returns true. The output is 1.

For {1, 3, 2}, the check at index 1 finds 3 greater than 2, so it returns false at once. The output is 0. Equal neighbors count as sorted, because the test is >, not >=. That is a choice you should state in an interview. "Sorted" usually means non-decreasing, which allows equal values.

Notice the braces in the call isSorted({1, 2, 2, 5}, 0). C++ builds a temporary vector from the list and passes a reference to it. The temporary lives until the end of the full expression, which is long enough for the call to finish.

Worked example 3: read an array from input

Real programs read their data. The next program reads a count, then that many numbers, and reports the sum, the maximum and whether the array is sorted. It is the same three ideas as before, now working on data you type.

Type this into the Input box and press Run:

5
3 9 2 7 1

The first line is the count, 5. The second line holds the five numbers, separated by spaces. The output is:

sum 22
max 9
sorted no

Notice what the program does with the count. The vector is sized from n before reading, so a already has five slots. The recursive functions use a.size() to find the end, so they never need n again. That keeps each function honest: it works for any vector, not only the one that was typed.

The variable sumFrom returns long long, although the elements are int. A sum of many large ints can overflow an int. Using a wider type for the running total is a standard habit. Adding 2,000,000,000 twice would already overflow a 32-bit int, which holds values up to about 2.1 billion.

Try the input 4 then 1 2 3 4. The sum is 10, the max is 4 and the array is sorted, so the output reads sorted yes. Then try 0 with no numbers. The sum is 0, but maxFrom would read a[0] on an empty vector. This is the empty-input edge case from earlier, and the fix is to check n == 0 before calling maxFrom. Add that check in your own version.

Worked example 4: binary search, halving the range

Binary search works on a sorted array. It looks at the middle element. If the middle equals the target, it is found. If the target is larger, it can only be in the right half, so the search continues there. If the target is smaller, it continues in the left half. Each step throws away half the remaining range.

Think of a phone book. You open it near the middle, see the name, and decide which half holds the name you want. You never read the other half. That is the same idea, and it is why binary search takes only about 20 steps to search a list of a million names.

The recursive version passes lo and hi, the ends of the range that could still hold the target.

Type this into the Input box and press Run:

7
1 3 5 7 9 11 13
9

The output is:

found at index 4

Trace it. The range is indexes 0 to 6. The middle is 3, which holds 7. The target 9 is larger, so the search moves to the right half, indexes 4 to 6. The middle is 5, which holds 11. The target is smaller, so the search moves to the left half, indexes 4 to 4. The middle is 4, which holds 9. That matches, and the function returns 4.

Only three values were looked at. A linear scan from the start would have looked at five. On a list of a million sorted values, binary search looks at about 20 values, while a scan could look at a million.

The base case lo > hi is the empty range. It is different from lo == hi, which is still one element that can match. Using the wrong comparison is a classic bug. If the base case were lo == hi, the function would never check the single remaining element when it was the target at the last step, and it would return -1 for a target that is present.

The line mid = lo + (hi - lo) / 2 looks more complicated than (lo + hi) / 2. It avoids overflow. If lo and hi are both near the largest int, their sum can be larger than an int can hold. The subtraction hi - lo is always small and safe.

Step through the animation above and watch the range shrink. Note how each step cuts the range in half, and how the recursion depth is about log base 2 of n. That depth is the stack space used by this version.

The search range halving at each step, from seven values to one

Worked example 5: reverse an array in place with two ends

The last runnable program reverses a list of numbers. It uses the two-ends shape with swaps, which is the same as reverseStr but on a vector. It also shows how to print a list with spaces between values, without a trailing space.

Type this into the Input box and press Run:

5
1 2 3 4 5

The output is:

5 4 3 2 1

The function takes vector<int>& without const, because it changes the vector. Each call swaps one pair, using a temporary variable tmp, which holds one value while the other moves. Without tmp you would lose one of the values. Trace it: the first call swaps 1 and 5, giving 5 2 3 4 1. The second call swaps 2 and 4, giving 5 4 3 2 1. The third call has lo equal to 2 and hi equal to 2, so the base case returns without a swap. The middle element 3 is never moved, which is right for an odd count.

The base case is lo >= hi, which handles both an even count and an odd count. For an even count, the last call has lo one less than hi and swaps once more. For an odd count, the last call has lo equal to hi. In both cases the check stops the recursion.

The output loop puts a space before every value except the first. This is a common pattern: print a separator before each item after the first, instead of after each item. The result has no trailing space, which some judges reject.

Index arithmetic and the two common base cases

Most bugs in this lesson come from one of two base cases. Learn them as a pair.

For the one-index shape, the base case is at the end. Call it i == n when the function handles the element at i and then moves on, so the empty tail is i == n. Call it i == n - 1 when the function returns the last element as its own answer, as maxFrom does. Pick the one that matches what the base returns, and check the empty input.

For the two-ends shape, the base case is lo >= hi. It covers an even length, where the two ends can cross without becoming equal, and an odd length, where they meet on the middle element. Using lo == hi breaks for even lengths, because lo can jump past hi.

Write the base case with >= or <= even when you are sure the values will be equal. It costs nothing, and it protects you from the crossing case.

Working with strings: the substring approach

A string is also a sequence, and you may see recursion written with substr. The idea is to take the first character and recurse on the rest. The code is short, but it has a cost.

bool isPalSlow(const string& s) {
    if (s.size() <= 1) return true;
    if (s.front() != s.back()) return false;
    return isPalSlow(s.substr(1, s.size() - 2));
}

Each call creates a new string with substr. For a string of length n, the calls create strings of length n, n minus 2, and so on, so the total copying is about n squared divided by 2. The version with two indexes never copies anything. In an interview, the index version is the one to write, and you can mention the substring version as a shorter idea that costs more memory and time.

Complexity

Let n be the number of elements or characters.

• sumFrom, maxFrom, sortedFrom and isSorted each make about n calls, so time is O(n). Their stack depth is also n, so extra space is O(n).
• isPal and reverseStr make about n divided by 2 calls. Time is O(n), and the stack depth is also about n divided by 2, which is O(n).
• search in binary search makes about log base 2 of n calls, so time is O(log n). Its stack depth is the same, so extra space is O(log n). An iterative version with a loop uses O(1) extra space.
• The substring version of palindrome costs O(n squared) in time, because it copies the string on each call.

Do not confuse the number of calls with the work inside each call. A call that copies a vector is not O(1) work, even though it looks like one line.

Worked example 7: count the matches

The last pattern is counting. It builds a number from smaller counts, the same way the sum did, with a test added. Here is a function that counts how many values equal a target.

int countEqual(const vector<int>& a, int i, int target) {
    if (i == (int)a.size()) return 0;
    int here = (a[i] == target) ? 1 : 0;
    return here + countEqual(a, i + 1, target);
}

Trace it on {4, 7, 4} with target 4. At index 0 the value is 4, so here is 1, and the call returns 1 plus the count from index 1. At index 1 the value is 7, so here is 0, and the call returns 0 plus the count from index 2. At index 2 the value is 4, so here is 1, and the call returns 1 plus the count from index 3. Index 3 is the end, so it returns 0. Now the answers climb: 1 + 0 is 1 at index 2, then 0 + 1 is 1 at index 1, then 1 + 1 is 2 at index 0. The answer is 2.

Notice that no variable is shared between calls. Each call adds its own 0 or 1 to the count from the rest, so no undo is needed. The time is O(n), and the stack depth is also n. A loop with one counter gives the same answer with O(1) extra memory, which is the same trade-off you have seen in every example in this lesson.

How deep can the recursion go?

Each call adds a frame, and the stack has a fixed size. On many Linux systems that size is about 8 megabytes. A recursive function over an array of one million elements makes one million calls. If each frame takes about 48 bytes, which depends on the compiler, that is about 48 megabytes of frames. The stack cannot hold that, so the program crashes. Eight megabytes holds only about 170,000 frames at that size.

So the rule of thumb is simple. Recursion over an array of a few thousand elements is safe. Recursion over hundreds of thousands is a risk. Binary search is safe even for a million elements, because its depth is about 20, which is the logarithm you saw earlier. The recursion depth is the number to check, and for the one-index shapes in this lesson the depth equals the array length.

The fix for long input is a loop. Here is the loop version of sumFrom. It uses one variable and no frames, so its memory does not grow with the array.

long long sumLoop(const vector<int>& a) {
    long long total = 0;
    for (int x : a) total += x;
    return total;
}

The range-based loop for (int x : a) reads each element once, in order. It is the same pattern as the recursion, with the frames replaced by one running total. In an interview, a good answer is "I would write the recursion for clarity, and a loop if the input can be large." That answer shows you know the trade-off.

A preview: merge sort uses two indexes

Two-index recursion appears in sorting too. Merge sort splits an array into halves, sorts each half by calling itself, and then merges the two sorted halves. The merge walks both halves with two indexes that move forward, and at each step it copies the smaller front value. The halves are the smaller copies, and the merge is the small step that combines their answers. You will meet the full algorithm in the divide and conquer module. For now, notice that the answer is built on the way up, as in the sum example, and that the merge itself is a loop with two indexes, not a recursion.

Common mistakes and the messages you will see

Mistake 1: index past the end. A vector does not check its bounds when you use []. The next program reads one element past the end. It may print garbage, or it may crash.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> a = {1, 2, 3};
    cout << a[3] << "\n";
    return 0;
}

The program reads memory past the end of the vector, because a[3] is outside it. On the g++ used to check this lesson, the program stops with an assertion instead of printing a number:

Assertion '__n < this->size()' failed.

Other setups may print a random number and carry on, which is harder to notice. Use a.at(3) when you want a clear error. With at, the program stops with a message like this:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)

The fix is in the base case. The one-index function must not read a[i + 1] when i is the last index. isSorted checks i >= size - 1 first for this reason.

Mistake 2: passing by value. This compiles and gives the right answer, but it is much slower. The fix is to write const vector<int>&. The program still works without the &, so the mistake is silent. You notice it only when the input is large.

Mistake 3: the wrong base case for palindromes. The check lo == hi misses even-length strings. The string "abba" goes (0, 3), then (1, 2), then (2, 1). The pair (2, 1) never equals, so the function would recurse forever if the base case were only equality. The fix is lo >= hi.

Mistake 4: forgetting that the array changes. When a function swaps elements, the caller sees the change, because it passed a reference. A reader of your code might not expect that. Mark changing parameters with a plain & and read-only ones with const, so the intent is visible.

Mistake 5: forgetting the empty input. maxFrom on an empty vector reads a[0] of nothing, and the program may crash or print garbage. Check for empty input in the caller, before the recursion starts.

Debugging walkthrough

Here is a palindrome checker with a bug. It returns the wrong answer for "abba".

#include <iostream>
#include <string>
using namespace std;
 
bool isPal(const string& s, int lo, int hi) {
    if (lo == hi) return true;              // bug: only equality
    if (s[lo] != s[hi]) return false;
    return isPal(s, lo + 1, hi - 1);
}
 
int main() {
    cout << isPal("abba", 0, 3) << "\n";
    return 0;
}

Run it and the program stops with a crash. The pairs go (0, 3), (1, 2), (2, 1), (3, 0), and then (4, -1), and the base case lo == hi never fires for them, so the calls continue until they read a character outside the string. On the g++ used to check this lesson, the stop is an assertion, Assertion '__pos <= size()' failed. Add a print line on entry to see the pairs. Use endl so the lines are flushed before the crash:

isPal lo=0 hi=3
isPal lo=1 hi=2
isPal lo=2 hi=1
isPal lo=3 hi=0

The printed pairs show the cause at once. lo and hi cross, and they never become equal. The fix is to write if (lo >= hi) return true;. With that change the pair (2, 1) hits the base case and the program prints 1.

The method is simple. Print the arguments on each entry, look at the sequence of values, and find the first value that breaks your assumption. Here the assumption was that lo and hi meet exactly. The printed sequence shows they can cross.

Variations and edge cases

Linear search. Return the index of the first match, or -1. The base case is past the end. Each call compares one element and either returns the index or moves on.

Counting matches. Return how many elements equal a target. Each call adds 1 or 0 to the answer from the rest. This is the sum pattern, with a test before the addition.

Checking the whole array for a property. Many properties, such as all values even, follow the isSorted pattern. Return false at the first failure, otherwise recurse. This stops early, which can be faster than checking everything.

Duplicates. A palindrome check that ignores case or punctuation needs a different test at each step. The pattern is the same: skip characters that do not count, then compare the next pair.

Merging two sorted halves. Merge sort, which you will meet in the divide and conquer module, combines two sorted arrays with two indexes that move forward. It is a two-pointer loop, but it is also a recursive idea, because the sorting of each half is a smaller copy of the same task.

Interview questions

These questions appear often. Answer each in a few sentences, with the base case and the complexity.

• Write a recursive function that reverses an array. What is the base case, and why is it lo >= hi? Answer by naming the two ends and the crossing case for even and odd lengths.
• Write a recursive check that a string is a palindrome. Answer with the two-ends shape, and say why the index version is better than the substring version.
• Why does binary search take O(log n) time? Answer with the halving at each step and the call depth.
• What is the difference between passing vector<int> and passing const vector<int>&? Answer with the copy on each call.

Real-world uses

These patterns show up in software you use. A text editor checks a selected word for a palindrome during a word game. A search box in a sorted list of prices uses binary search over the index. A log tool checks that timestamps are in order with a sorted check. A tool that reverses a string for display uses two ends, and a spell checker that ignores case compares characters from both ends. Each one is a small recursive function or a loop with the same two-index idea.

Practice

Write each exercise in your own editor before you open the solution.

1. Write int countChar(const string& s, int i, char c) that returns how many times c appears in s, using recursion from index i. Hint: add 1 when s[i] == c, then add the count from the rest. Test with "banana" and 'a', which should give 3.

int countChar(const string& s, int i, char c) {
    if (i == (int)s.size()) return 0;
    return (s[i] == c ? 1 : 0) + countChar(s, i + 1, c);
}

2. Write int linearSearch(const vector<int>& a, int i, int target) that returns the index of the first target, or -1 when it is absent. Test with {4, 8, 15} and 15, which should return 2.

int linearSearch(const vector<int>& a, int i, int target) {
    if (i == (int)a.size()) return -1;
    if (a[i] == target) return i;
    return linearSearch(a, i + 1, target);
}

3. Write bool allEven(const vector<int>& a, int i). It returns true when every element is even. Test with {2, 4, 6} and {2, 5, 6}.

bool allEven(const vector<int>& a, int i) {
    if (i == (int)a.size()) return true;
    if (a[i] % 2 != 0) return false;
    return allEven(a, i + 1);
}

4. Trace search for the target 2 in the sorted array {1, 2, 4, 6, 8}. Write down each range (lo, hi) and each middle index before you run it. Then check your trace against the program.

5. Write void reverseCopy(const vector<int>& a, int i, vector<int>& out) that adds the elements of a to out in reverse order, without changing a. Hint: recurse first, then push the current element.

void reverseCopy(const vector<int>& a, int i, vector<int>& out) {
    if (i == (int)a.size()) return;
    reverseCopy(a, i + 1, out);
    out.push_back(a[i]);
}

6. A student writes bool isSorted(const vector<int>& a, int i) { if (i == a.size()) return true; if (a[i] > a[i+1]) return false; return isSorted(a, i + 1); }. Explain why it fails on the last element, and fix it.

7. Write int maxIndex(const vector<int>& a, int i) that returns the index of the largest value, using recursion from index i. Test with {3, 9, 2, 9} where the answer is 1, since the first largest value wins.

int maxIndex(const vector<int>& a, int i) {
    if (i == (int)a.size() - 1) return i;
    int best = maxIndex(a, i + 1);
    return (a[i] >= a[best]) ? i : best;
}

8. Write bool isPalWords(const string& s, int lo, int hi) that ignores spaces, so "never odd or even" counts as a palindrome. Hint: skip a space on either end by moving that end, then compare.

bool isPalWords(const string& s, int lo, int hi) {
    if (lo >= hi) return true;
    if (s[lo] == ' ') return isPalWords(s, lo + 1, hi);
    if (s[hi] == ' ') return isPalWords(s, lo, hi - 1);
    if (s[lo] != s[hi]) return false;
    return isPalWords(s, lo + 1, hi - 1);
}

9. Explain in two sentences why the binary search from this lesson is O(log n) and the linear search from exercise 2 is O(n) in the worst case.

10. Write a recursive void printArray(const vector<int>& a, int i) that prints the values separated by spaces with no trailing space, and then test it with an empty vector and with {7}. Explain what the output is for each.

void printArray(const vector<int>& a, int i) {
    if (i == (int)a.size()) return;
    if (i > 0) cout << " ";
    cout << a[i];
    printArray(a, i + 1);
}

What you now know

• Pass a position, such as an index or a pair of indexes, instead of copying a smaller array.
• Use const vector<int>& for read-only input and a plain reference for input you change.
• The one-index shape walks forward, and its base case is the end of the array.
• The two-ends shape walks inward, and its base case is lo >= hi, which covers both even and odd lengths.
• Binary search halves the range on each call, so it takes O(log n) time.
• Watch the empty input and the last index, because those cause most bugs in this kind of code.