Recursion Problem Solving II: Array Traversal, Sorting Check and Reversal

9
0

Recursion Problem Solving - II

Arrays are naturally suited to recursive processing because an array range can be divided into a current element and a smaller remaining range. A recursive function can process one index and delegate the rest of the work to another call.

The most important step is to define the function's responsibility precisely. For example:

function(index) processes the array from index to its final valid position.

Once that responsibility is clear, the recurrence, base case, and initial call become easier to derive.

Problem 1: Print Every Array Element

Given an array, print all its elements in their original order.

For the array: 10 20 30 40

The required output is: 10 20 30 40

Iterative Approach

An array of size n has valid indexes from 0 to n - 1. An ordinary loop can therefore print array[index] for every index in this range.

Recursive Responsibility

Define printForward(index) as follows:

The function prints every element from index through the last valid index.

To satisfy that responsibility:

  • Print the element at the current index.

  • Ask the recursive call to print everything from the next index onward.

  • Stop when the index reaches the array's size.

The recurrence is conceptually:

printForward(index) = print array[index], then printForward(index + 1)

Tail-Recursive Forward Traversal

When printing occurs before the recursive call, the values are produced while the call stack is growing. Since the recursive call is the final operation, this follows a tail-recursive form.

Head-Recursive Forward Traversal

The array can also be printed in normal order by starting at the final index and making recursive calls toward index zero before printing.

For an initial index of n - 1:

  • Recursively process index - 1.

  • Print the current element after the smaller call returns.

  • Stop after the index becomes negative.

The calls move from the final index toward zero, but printing occurs during stack unwinding. This restores the original left-to-right order.

Printing an Array in Reverse Order

To print the array from right to left, begin at n - 1, print the current element immediately, and recursively process index - 1.

#include <iostream>
#include <vector>
using namespace std;
void printForward(int index, const vector<int>& values) {
if (index == values.size()) {
return;
}
cout << values[index] << ' ';
printForward(index + 1, values);
}
void printForwardFromEnd(int index, const vector<int>& values) {
if (index < 0) {
return;
}
printForwardFromEnd(index - 1, values);
cout << values[index] << ' ';
}
void printReverse(int index, const vector<int>& values) {
if (index < 0) {
return;
}
cout << values[index] << ' ';
printReverse(index - 1, values);
}
int main() {
vector<int> values{10, 20, 30, 40};
printForward(0, values);
cout << '\n';
printForwardFromEnd(values.size() - 1, values);
cout << '\n';
printReverse(values.size() - 1, values);
cout << '\n';
}

Dry Run of Head-Recursive Forward Printing

For {10, 20, 30, 40}, the initial call uses index 3:

  • Index 3 calls index 2.

  • Index 2 calls index 1.

  • Index 1 calls index 0.

  • Index 0 calls index -1.

  • Index -1 reaches the base case.

The calls then resume in reverse order:

  • The frame for index 0 prints 10.

  • The frame for index 1 prints 20.

  • The frame for index 2 prints 30.

  • The frame for index 3 prints 40.

Complexity Analysis

  • Time complexity: O(n).

  • Recursive stack space: O(n).

Problem 2: Find the Maximum and Minimum

Given a non-empty integer array, find its maximum and minimum values.

For the array: 5 8 2 6

  • The maximum is 8.

  • The minimum is 2.

Iterative Current-Champion Approach

An iterative maximum search treats the first element as the current champion. Starting from index 1, every larger value replaces that champion.

The minimum search follows the same pattern but replaces the champion when a smaller value is found.

Initializing from an actual array element is safer than using an arbitrary value such as zero. An all-negative array would otherwise produce an incorrect maximum.

Recursive Function Definition

Define findMaximum(index) as:

The maximum element in the range from index through n - 1.

The current answer is the larger of:

  • The element at the current index.

  • The maximum returned for the remaining range.

Therefore: findMaximum(index) = max(array[index], findMaximum(index + 1))

When index is already the last valid index, only one element remains. That element is both the maximum and minimum of the one-element range.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int findMaximum(int index, const vector<int>& values) {
if (index == values.size() - 1) {
return values[index];
}
int maximumInRest = findMaximum(index + 1, values);
return max(values[index], maximumInRest);
}
int findMinimum(int index, const vector<int>& values) {
if (index == values.size() - 1) {
return values[index];
}
int minimumInRest = findMinimum(index + 1, values);
return min(values[index], minimumInRest);
}
int findMaximumBackward(int index, const vector<int>& values) {
if (index == 0) {
return values[0];
}
int maximumInRest = findMaximumBackward(index - 1, values);
return max(values[index], maximumInRest);
}
int findMinimumBackward(int index, const vector<int>& values) {
if (index == 0) {
return values[0];
}
int minimumInRest = findMinimumBackward(index - 1, values);
return min(values[index], minimumInRest);
}
int main() {
vector<int> values{5, 8, 2, 6};
cout << findMaximum(0, values) << '\n';
cout << findMinimum(0, values) << '\n';
cout << findMaximumBackward(values.size() - 1, values) << '\n';
cout << findMinimumBackward(values.size() - 1, values) << '\n';
}

Forward Dry Run for 5, 8, 2, 6

The recursive calls expand as follows:

  • maximum(0) = max(5, maximum(1))

  • maximum(1) = max(8, maximum(2))

  • maximum(2) = max(2, maximum(3))

  • maximum(3) = 6

The answers return as follows:

  • maximum(2) = max(2, 6) = 6

  • maximum(1) = max(8, 6) = 8

  • maximum(0) = max(5, 8) = 8

Alternative Dry Run for 8, 6, 10

  • The final index returns 10.

  • The previous call compares 6 and 10, returning 10.

  • The first call compares 8 and 10, returning 10.

The comparison is performed after each deeper call returns. Therefore, this is a return-based recursive pattern rather than a true tail-recursive function.

Complexity Analysis

  • Time complexity: O(n).

  • Recursive stack space: O(n).

These functions require a non-empty array because their base cases return an existing element.

Problem 3: Count Occurrences of a Target

Given an array and a target, count how many times the target appears.

For: array = {10, 20, 10, 10} and target = 10

The answer is 3.

Recursive Responsibility

Define countOccurrences(index) as the number of target occurrences from index through the final array position.

The current index contributes:

  • 1 when array[index] == target.

  • 0 otherwise.

The recurrence is: currentContribution + countOccurrences(index + 1)

When the index reaches the array's size, no elements remain, so the function returns zero.

#include <iostream>
#include <vector>
using namespace std;
int countOccurrences(int index, const vector<int>& values, int target) {
if (index == values.size()) {
return 0;
}
int current = values[index] == target ? 1 : 0;
return current + countOccurrences(index + 1, values, target);
}
int countOccurrencesBackward(int index, const vector<int>& values, int target) {
if (index < 0) {
return 0;
}
int current = values[index] == target ? 1 : 0;
return current + countOccurrencesBackward(index - 1, values, target);
}

Dry Run

For {10, 20, 10, 10} and target 10:

  • Index 0 matches and contributes 1.

  • Index 1 does not match and contributes 0.

  • Index 2 matches and contributes 1.

  • Index 3 matches and contributes 1.

  • Index 4 reaches the base case and contributes 0.

The final result is: 1 + 0 + 1 + 1 + 0 = 3

Counting is not direction-sensitive, so the function can traverse from left to right or right to left.

Complexity Analysis

  • Time complexity: O(n).

  • Recursive stack space: O(n).

Given an array and a target, return the index of the target's first occurrence. Return -1 when the target is absent.

For array = {10, 20, 30, 40, 50}

  • Searching for 30 returns index 2.

  • Searching for 300 returns -1.

Finding the First Occurrence

The traversal must proceed from left to right:

  • If the current index is beyond the array, return -1.

  • If the current element matches, return the current index immediately.

  • Otherwise, search the smaller range beginning at the next index.

Returning immediately on the first match guarantees that the smallest matching index is selected.

Finding the Last Occurrence

The last occurrence can be found by starting at the final index and searching toward zero. The first match encountered during that backward traversal is the array's last occurrence.

#include <iostream>
#include <vector>
using namespace std;
int firstOccurrence(int index, const vector<int>& values, int target) {
if (index == values.size()) {
return -1;
}
if (values[index] == target) {
return index;
}
return firstOccurrence(index + 1, values, target);
}
int lastOccurrence(int index, const vector<int>& values, int target) {
if (index < 0) {
return -1;
}
if (values[index] == target) {
return index;
}
return lastOccurrence(index - 1, values, target);
}
int main() {
vector<int> values{10, 20, 30, 20, 40};
cout << firstOccurrence(0, values, 20) << '\n';
cout << lastOccurrence(values.size() - 1, values, 20) << '\n';
}

For this array, the first occurrence of 20 is at index 1, while the last is at index 3.

Complexity Analysis

  • Time complexity: O(n) in the worst case.

  • Recursive stack space: O(n).

Problem 5: Check Whether an Array Is Sorted

Given an integer array, determine whether it is sorted in non-decreasing order.

In non-decreasing order, equal adjacent values are allowed.

  • {10, 20, 30, 30} is sorted.

  • {10, 5, 6, 7} is not sorted.

Adjacent-Pair Observation

An array is sorted in non-decreasing order when every element from index 1 onward is at least as large as its previous element.

If any position satisfies: array[index] < array[index - 1]

the array is not sorted.

Recursive Responsibility

The function begins at index 1 because every comparison uses the current element and its predecessor.

  • If the index reaches the array's size, every adjacent pair has passed; return true.

  • If the current element is smaller than the previous element, return false.

  • Otherwise, recursively check the next pair.

#include <iostream>
#include <vector>
using namespace std;
bool isSorted(int index, const vector<int>& values) {
if (index == values.size()) {
return true;
}
if (values[index] < values[index - 1]) {
return false;
}
return isSorted(index + 1, values);
}
int main() {
vector<int> first{10, 20, 30, 30};
vector<int> second{10, 5, 6, 7};
cout << isSorted(1, first) << '\n';
cout << isSorted(1, second) << '\n';
return 0;
}

The first call prints 1, representing true. The second prints 0, representing false.

An empty array and a one-element array are sorted by definition. Calling the function with index 1 causes the base case to return true immediately for those sizes.

Early Termination

The function stops as soon as it finds one invalid adjacent pair. It does not need to inspect later elements because a single violation is sufficient to prove that the array is not sorted.

Complexity Analysis

  • Time complexity: O(n) in the worst case.

  • Recursive stack space: O(n).

Problem 6: Reverse an Array In Place

Given an array, reverse its elements without constructing another array.

For: {10, 20, 30, 40}

The reversed array is: {40, 30, 20, 10}

Two-Pointer Approach

Use two indexes:

  • left begins at index 0.

  • right begins at index n - 1.

Swap the elements at the two indexes, move left one position forward, and move right one position backward. The process ends when the indexes meet or cross.

Recursive Responsibility

Define reverseArray(left, right) as:

Reverse the array segment from left through right.

The current call swaps the outermost pair. The recursive call then reverses the smaller inner segment:

reverseArray(left + 1, right - 1)

When left >= right, the segment contains at most one element and is already reversed.

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
void reverseIterative(vector<int>& values) {
int left = 0;
int right = values.size() - 1;
while (left < right) {
swap(values[left], values[right]);
left++;
right--;
}
}
void reverseRecursive(int left, int right, vector<int>& values) {
if (left >= right) {
return;
}
swap(values[left], values[right]);
reverseRecursive(left + 1, right - 1, values);
}
int main() {
vector<int> values{10, 20, 30, 40};
reverseRecursive(0, values.size() - 1, values);
for (int value : values) {
cout << value << ' ';
}
cout << '\n';
}

Dry Run for 10, 20, 30, 40

  • Call reverseRecursive(0, 3).

  • Swap 10 and 40, producing {40, 20, 30, 10}.

  • Call reverseRecursive(1, 2).

  • Swap 20 and 30, producing {40, 30, 20, 10}.

  • Call reverseRecursive(2, 1).

  • The pointers have crossed, so recursion stops.

Why This Is In-Place

The same vector is modified through a non-constant reference. No second array proportional to the input size is created.

The algorithm uses O(1) auxiliary data outside recursion, although the recursive calls still consume O(n) stack space.

Complexity Analysis

  • Time complexity: O(n).

  • Explicit auxiliary space: O(1).

  • Recursive stack space: O(n).

Forward and Backward Recursive Traversal

Many array problems can be solved from either direction, but the direction must match the required result.

  • Counting occurrences can proceed in either direction.

  • Maximum and minimum can proceed in either direction.

  • Printing can use either direction when work is positioned correctly around the call.

  • First-occurrence search naturally proceeds from left to right.

  • Last-occurrence search naturally proceeds from right to left.

  • Sortedness can be checked in either direction as long as adjacent elements are compared correctly.

Choosing an Array Base Case

Different recursive responsibilities require different stopping conditions.

  • Forward traversal stops when index == size.

  • Backward traversal stops when index < 0.

  • Maximum or minimum over a non-empty suffix stops at index == size - 1.

  • Maximum or minimum over a non-empty prefix stops at index == 0.

  • Two-pointer reversal stops when left >= right.

The base case must correspond to the exact meaning assigned to the function. Using the wrong boundary commonly causes skipped elements or out-of-range access.

Common Mistakes

  • Using index > size instead of stopping when index == size.

  • Accessing array[index] before checking whether the index is valid.

  • Starting a sortedness check at index zero and then reading index -1.

  • Returning an arbitrary value such as zero for the maximum of an all-negative array.

  • Forgetting that maximum and minimum functions require a non-empty input.

  • Traversing backward when the first occurrence from the left is required.

  • Continuing the search after finding the first required match.

  • Passing a vector by value and unintentionally copying it during every recursive call.

  • Passing an array as constant when the function must reverse it in place.

  • Using left > right as the only stopping condition when no work is needed for the middle element either.

General Recursive Array Pattern

A useful template for recursive array processing is:

  • Define what the function does for the range beginning at the current index.

  • Check whether the range is empty or has reached a directly solvable size.

  • Process the current element or boundary pair.

  • Call the function on the smaller remaining range.

  • Combine the current result with the returned result when necessary.

Key Takeaways

  • An index allows a recursive function to represent an array suffix or prefix.

  • Printing before a recursive call produces output during stack growth.

  • Printing after a recursive call produces output during stack unwinding.

  • Maximum and minimum combine the current element with an answer returned for a smaller range.

  • Counting occurrences adds either zero or one for each index.

  • First-occurrence search must preserve left-to-right priority.

  • A sortedness check needs only one invalid adjacent pair to return false.

  • In-place reversal recursively shrinks a two-pointer range.

  • Passing arrays by reference avoids unnecessary copies.

  • Every recursive function must define its range and base case precisely.

C++

Read Similar Blogs

C++

Recursion Problem Solving I: Power, Digit Sum and Number Reversal

Recursion Problem Solving - I Recursive problem solving begins by defining exactly what a function should return. The current problem is then expressed in terms of the same function applied to a sm...

8
C++

Recursion in C++ Explained: Base Cases, Call Stack and Recursive Functions

Recursion Foundation and Call Flow Recursion is a problem-solving technique in which a function calls itself with a smaller version of the original problem. Each call handles one part of the work a...

9
C++

C++ Enums Explained: Enum Class, Scoped Enumerations and State Modelling

cpp #include using namespace std; int main() { int orderStatus = 3; if (orderStatus == 3) { cout << "The order cannot be cancelled\n"; } } python java javascript c mysql postgres tuf-code-editor-1...

6
Comments0