Day 14 of 60 Days of DSA — Recursion II

Fast Power & Finding All Indices in an Array

Thumbnail-Image

Recursion often feels comfortable when problems are small.

But the real test of understanding begins when recursion is used to optimise performance or systematically explore data.

On Day 13, we learned how recursion works through foundational problems.
Today, on Day 14, we take the next step — using recursion to reduce time complexity and replace iterative scans with clean, structured logic.

We’ll solve two classic problems:

  1. Fast Power (Exponentiation by Recursion)
  2. Finding All Indices of a Target Element in an Array

Both are frequently used to evaluate how well you understand recursive thinking beyond basics.

Problem 1: Fast Power

Problem Description

Given two positive integers A and B. Implement Fast Power function to compute AB

Problem Constraints

AB would fit in 64-bit type integer.

Example Input

Input 1 :
A = 2 , B = 10
Input 2 :
A = 1 , B = 100000000

Example Output

Output 1 :
1024
Output 2 :
1

Example Explanation

For Input 1 :
210 = 25 * 25
25 = 32, so 32 * 32 = 1024
For Input 2 :
1 raised to power anything is 1

Why Not Use a Loop?

A simple loop multiplies A exactly B times:

  • Time Complexity: O(B)
  • This becomes inefficient when B is large

Fast Power reduces this dramatically by observing a key mathematical insight.

Recursive Intuition (Step-by-Step)

Intuition

Let’s say:

A = 2, B = 10
  1. Compute power(2, 5)
  2. Compute power(2, 2)
  3. Compute power(2, 1) → base case
  4. Build the result back while returning

Each recursive call halves B.

Base Cases

  • If B == 0 → return 1
  • If B == 1 → return A

These stop unnecessary recursion.

Code (JavaScript)

function power(A, B){
 A = BigInt(A);
 B = BigInt(B);

 if(B == BigInt(1)) return A;
 if(B == BigInt(0)) return BigInt(1);

 let half = power(A, B/BigInt(2));
 if(B%BigInt(2) == BigInt(0)){
 return half* half;
 }else{
 return A * half* half;
 }
}

Time & Space Complexity

  • Time Complexity: O(log B)
  • Space Complexity: O(log B) (recursion stack)

Problem 2: All Indices Of Array

Problem Description

Given an array of integers A with N elements and a target integer B, the task is to find all the indices at which B occurs in the array.

Note: The problem encourages recursive logic for learning purposes. Although the online judge doesn’t enforce recursion, it’s recommended to use recursive solutions to align with the question’s spirit.

Example Input

Input 1:
A = [1, 2, 3, 4, 5]
B = 1
Input 2:
A = [8, 9, 5, 6, 5, 5]
B = 5

Example Output

Output 1:
[0]
Output 2:
[2, 4, 5]

Example Explanation

Explanation 1:
The Target, 1 occurs on Index = 0. So returning [0]
Explanation 2:
Here, the target 5 occurs at indexes [2, 4, 5].

Recursive Strategy

We traverse the array one index at a time:

  1. If index exceeds array length → stop recursion
  2. If current element matches target → store index
  3. Recur for the next index

Code (JavaScript)

function main(A, B){
 let arr = [];
 function findB(A,i,B){
 if(i >= A.length) return;
 if(A[i] == B){
 arr.push(i);
 }
 findB(A, i+1, B);
 }
 findB(A, 0, B);
 return arr;
}

Time & Space Complexity

  • Time Complexity: O(N)
  • Space Complexity: O(N) (recursion stack + result array)

Final Thoughts

Today’s problems show two important uses of recursion:

  • Optimization (Fast Power)
  • Systematic traversal (All Indices)

If you truly understand these patterns, recursion stops feeling magical and starts feeling logical.

In the next days, recursion will become even more powerful when combined with:

  • Backtracking
  • Divide & Conquer

Until then, keep practicing and tracing recursive calls on paper — it’s the fastest way to master them.

Do you want to solve more with us?

Then follow this series and share your progress in the comments.

If the topics are difficlt for you to understand, then you can refer to the notes on my GitHub.

Here’s the Code link

At Dev Simplified, We Value Your Feedback 📊

👉 Let us know how you’re finding this series so far. It motivates us to write and provide valuable content for you.

👉 Follow us to not miss any updates.

👉 Subscribe for free and join our growing community!