Recursion on Arrays: Reverse an Array
Reversing an array recursively utilizes a **two-pointer approach**. We maintain a left pointer ($L$) starting at index $0$ and a right pointer ($R$) starting at index $len - 1$.
The recursive algorithm is structured as:
- Base Case:
l >= r. When the pointers cross or meet in the middle, the array is fully reversed, and the recursion halts. - Swap Process: Swap elements at index $L$ and index $R$.
- Recursive Step: Increment $L$ by 1, decrement $R$ by 1, and make the recursive call:
reverse(l + 1, r - 1, arr).
Complexity Analysis
Time Complexity: O(N)
Since each recursive call processes 2 elements (one swap) and we swap $N/2$ times, the execution runs in linear time $O(N)$.
Space Complexity: O(N)
At the deepest recursion level, there are $N/2$ stack frames on the Call Stack. Thus, the auxiliary space is bounded by $O(N)$.