Implementing Backtracking with Recursive Function Calls

Implementing Backtracking with Recursion

Backtracking is a way of solving problems by trying one choice at a time. When a choice does not lead to an answer, you go back and try a different one. The cleanest way to write this in code is with recursion — a function that calls itself.

The big idea

Think of solving a problem as a journey between states. A state is just "where you are right now" — the partial answer you have built so far.

• You start at the initial state (an empty or starting answer).
• Each function call makes one choice, which moves you to a new state.
• You keep calling deeper and deeper until you reach a terminal state — a point where the answer is complete.
• At a terminal state, you use a validation check to decide: is this a real solution or not?

If a state is *not* a solution, that function call simply ends and returns control to the caller — the state you came from. From there you can try a new choice, keep going, or backtrack even further up. This "return and try something else" behavior is exactly what recursion gives you for free, because each function call remembers where it came from.

A concrete example: cracking a 4-digit binary password

Imagine a phone password made only of 0s and 1s, and it is 4 characters long. We want to generate every possible password until we find the right one.

Here is the C++ version:

#include <iostream>
#include <string>
using namespace std;

const string password = "0101";

void crackPassword(string state) {
    if (state.length() == 4 && state == password) {
        cout << "Password cracked" << endl;
    }
    if (state.length() == 4) {
        return;
    }
    for (int i = 0; i <= 1; i++) {
        string newState = state + (char)('0' + i);
        crackPassword(newState);
    }
}

Let's walk through what happens:

1. state holds the password we have built so far. We start with an empty string "".
2. Terminal check: if state is 4 characters long *and* equals password, we print "Password cracked".
3. Stop condition: if state is 4 characters long (full length), we return. There is nothing more to add, so this branch ends and control goes back to the caller. This return is the backtracking step.
4. Make choices: if the password is not full yet, the for loop tries both digits. (char)('0' + i) turns i = 0 into the character '0' and i = 1 into '1'. We add that digit to make newState, then call crackPassword(newState) to go one level deeper.

So the function grows the string one digit at a time: "" → "0" → "00" → "000" → "0000", checks it, returns, then tries "0001", and so on. It explores every branch like walking every path of a tree, backing up whenever a branch is finished.

Why this is backtracking

Notice we never manually "undo" anything. Because newState is a fresh copy passed into each call, when a call returns, the caller still has its own state unchanged. The loop then moves on to the next digit. That automatic "go back to where I was" is the heart of backtracking.

Complexity analysis

Why 2^N candidates? At every position in the password there are exactly two choices (0 or 1). For a password of length N, the total number of different passwords you can build is 2 × 2 × ... × 2 (N times) = 2^N. For our length-4 password that is 2^4 = 16 possible strings.

Space complexity — O(N): We never build any big data structure. The only thing that grows is the password string itself, which can be at most N characters long. So the memory used grows in line with N.

Time complexity: This measures how much work is done until the password is found.

• Best Case — O(N): The password is the very first string we generate. We only had to build one full string of length N, so the work is proportional to N.
• Worst Case — O(2^N): The password is the *last* string we generate, so we had to try all 2^N candidates first.

One important detail: the code above does not stop early after a match — there is no return right after printing "Password cracked". So if you measure the *total* runtime of the whole program, it always explores all 2^N candidates, making both best and worst cases O(2^N). If you wanted it to stop as soon as it found the answer, you would add an early exit after the match.

Key takeaways

• Backtracking is naturally written with recursion: each call = one choice, each return = one backtrack.
• Build the answer step by step; check it at the terminal state.
• Two choices per position over N positions gives 2^N total possibilities.
• Space is O(N) (just the growing string); time ranges from O(N) (lucky) to O(2^N) (unlucky or no early exit).