DSA Day 65: Recursion Meets Arrays & Optimization

📅 Date: June 16, 2026

🧠 Mood: The Data Wrangler 📊

🔥 Topic: DSA Day 65: Recursion Meets Arrays & Optimization

🚆 Theory Meets Reality

The past two days were a brutal re-introduction to logical problem solving. I mapped out the linear call stack, and I survived the branching nightmare of the Fibonacci sequence. But sitting on the train heading back to Thane today, I realized something: calculating factorials and Fibonacci numbers won't help me build real-world software.

In the industry, we don't process abstract math; we process data. Lists of users, streams of prices, arrays of information. Today, I took the training wheels off and applied recursive logic directly to Arrays. The objective was simple but mind-bending: Can I navigate, verify, and search an array without using a single for or while loop?

---

🔍 Shrinking the Search Space

When you iterate through an array with a loop, you move a pointer from index 0 to $N$. In recursion, you do the exact opposite. You look at the current element, and you pass the rest of the array to a smaller version of your function.

1. Is the Array Sorted?

The logic is incredibly elegant. Is an array sorted? Just check if arr[0] <= arr[1]. If it is, great! Now, assume the rest of the array (from index 1 onwards) is a brand new, smaller array. Call the function again on that smaller piece. If you reach the very end of the array without throwing a false, the entire thing is sorted.

2. The Direction of the Stack

Finding the First Occurrence of a number is easy: check the current index. If it matches, return it. If not, recurse.

But finding the Last Occurrence requires flipping the stack. You don't check the current index. You immediately recurse all the way to the end of the array, and you do your checking while the stack is collapsing backwards. It is a brilliant manipulation of memory.

---

💻 The Optimization Masterpiece: $X^N$

The highlight of today wasn't just arrays; it was calculating powers (like $2^{10}$). The naive recursive approach is to multiply $2 \times 2^{9}$, which takes $O(N)$ steps. But we can optimize this heavily using math: if $N$ is even, $X^N$ is exactly equal to $X^{N/2} \times X^{N/2}$.

#include <iostream>
using namespace std;

// Optimized Power Function - O(log N) Time Complexity
int powerOptimized(int x, int n) {
    // 1. BASE CASE
    if (n == 0) return 1;

    // 2. Calculate the half-power only ONCE
    int halfPower = powerOptimized(x, n / 2);
    int halfPowerSq = halfPower * halfPower;

    // 3. If N is odd, multiply by X one more time
    if (n % 2 != 0) {
        return x * halfPowerSq;
    }
    
    // 4. If N is even, just return the squared half
    return halfPowerSq;
}

int main() {
    int base = 2, exponent = 10;
    cout << base << " to the power of " << exponent << " is: " << powerOptimized(base, exponent) << endl;
    // Output: 2 to the power of 10 is: 1024
    return 0;
}

By calculating the half-power just once and squaring it, we cut the execution time exponentially. Calculating $2^{100}$ drops from 100 operations down to roughly 7 operations. That is the difference between a junior coder and a software engineer.

---

🎯 Bootcamp Complete

With the core mechanics of the Call Stack fully mapped out in my head, the 3-day Recursion bootcamp is officially complete. I now have the mental framework required to tackle the big leagues. It's time to prepare for Linked Lists and Trees. The real grind begins tomorrow.