Mohd Abdul Naveed

Posted on Feb 1

How to Know When a for Loop Belongs Inside Recursion

#algorithms #programming #recursion #computerscience

Many developers struggle with knowing when a for loop belongs inside a recursive function. The confusion isn’t about syntax, it’s about understanding what recursion is responsible for, and what it isn’t.

Why this matters in real code

I ran into this issue while solving backtracking problems and building traversal logic.

My recursive functions:

compiled ✔️
ran ✔️
looked correct ✔️

…but the results were incomplete or duplicated.
The bug wasn’t the recursion itself.

It was a misunderstanding when multiple choices must be explored at the same level.

A recursive function has two essential parts:

Base case — when to stop
Recursive call — how to move closer to that stop

Each recursive call:

creates a new stack frame
represents one level deeper in the problem

Call Stack (top)
┌─────────────┐
│ f(1)        │ ← last in
│ f(2)        │
│ f(3)        │
└─────────────┘
Call Stack (bottom)

Stacks are LIFO — last in, first out.

Problems with no branching (no loops)

Story: going down the stairs

Imagine a building with many floors.
Each recursive call moves you down one floor.
You stop at the ground floor — the base case.

int go_down(int floor) {
    if (floor == 0) return;
    go_down(floor - 1);
}

Floor 3
  ↓
Floor 2
  ↓
Floor 1
  ↓
Floor 0  (base case)

There is:

only one path
no choices

👉 No for loop belongs here

When loops become necessary

Now imagine each floor has multiple doors 🚪🚪🚪
Each door leads to the next floor.
That means:

Floors → recursion
Doors → loop

Visualizing the idea

Floor 3
 ├─ Door A → Floor 2
 ├─ Door B → Floor 2
 └─ Door C → Floor 2

Process:

Choose a door (loop)
Go down one floor (recursion)
Repeat

Code example: visiting rooms

void visit_rooms(int floor) {
    if (floor == 0) {
        cout << "Ground floor reached" << endl;
        return;
    }

    char doors[] = {'A', 'B', 'C'};
    for (char door : doors) {
        cout << "Using door " << door << " on floor " << floor << endl;
        visit_rooms(floor - 1);
    }
}

Why the loop exists

At the same level, you must try:

Door A
Door B
Door C Same level → loop Next level → recursion

When a loop does NOT belong

If there is only one action, looping is incorrect.

Countdown example

void countdown(int n) {
    if (n == 0) return;
    cout << n << endl;
    countdown(n - 1);
}

OutPut:

3 → 2 → 1 → 0

There is:

No choice
No doors
No flavors

Golden rule (remember this forever)

Recursion goes down
Loops go across

If these roles blur, your mental model breaks down.

A quick self-check

Ask:

“At this step, do I need to try multiple options?”

❌ No → no loop

✅ Yes → loop required

If you can’t name the options, the loop doesn’t belong.

A very common mistake

You:

have a base case
call the function recursively
get output

…but it’s missing results.

This happens when recursion is expected to handle branching.

It won’t.

Example: binary strings (classic pitfall)

Goal: generate all binary strings of length n

Expected output for n = 2:

❌ Incorrect approach

void generate(int n, string s) {
    if (n == 0) {
        cout << s << endl;
        return;
    }

    generate(n - 1, s + "0");
}

What actually happens

generate(2, "")
  → generate(1, "0")
    → generate(0, "00")

Only one path is explored.

What was missing?

At each level, there are two choices:

"" 
 ├─ "0"
 └─ "1"

👉 Recursion went down, but never sideways.

Think in terms of STATE (this is the mental unlock)

A recursive function always represents a state.
A state answers:

“Where am I right now?”
“What has already been decided?”

Examples of state:

current index
current depth
remaining steps
current path
current floor

Example

generate(2, "")

State:

depth = 2
string = ""

Next level (same depth, different choices):

generate(1, "0");
generate(1, "1");

Diagram:

Level 0: ""
 ├─ Level 1: "0"
 │   ├─ "00"
 │   └─ "01"
 └─ Level 1: "1"
     ├─ "10"
     └─ "11"

The rule (clearly stated)

Recursion moves between states
Loops explore multiple actions from the same state

Skip the loop → lose possibilities.

Classic example: permutations

Input

[1, 2, 3]

Output

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Step-by-step thinking

You build the permutation one position at a time.
At each step:

choose one unused number
try every possible choice

State definition

path → current permutation
used[] → which numbers are taken

void permute(vector<int>& nums, vector<int>& path, vector<bool>& used) {
    if (path.size() == nums.size()) {
        print(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;

        used[i] = true;
        path.push_back(nums[i]);

        permute(nums, path, used);

        path.pop_back();
        used[i] = false;
    }
}

Diagram

[]
 ├─ [1]
 │   ├─ [1,2]
 │   │   └─ [1,2,3]
 │   └─ [1,3]
 │       └─ [1,3,2]
 ├─ [2]
 │   ├─ [2,1]
 │   └─ [2,3]
 └─ [3]
     ├─ [3,1]
     └─ [3,2]

Why recursion alone isn’t enough
This line:

permute(nums, path, used)

does not automatically try other numbers.
Recursion:

moves deeper Loops:
create branches They solve different problems.

The real golden rule

Recursion answers: “What is the next state?”
Loops answer: “What are my options right now?”

If recursion is expected to replace branching, the algorithm will silently miss valid results.

Where you’ll see this pattern again

DFS / BFS
Backtracking problems
Tree traversals
Graph search
Combinatorics (subsets, permutations, combinations)

Once you separate state transitions from choice exploration, recursion problems become easier to reason about and debug.

DEV Community