Recursion Concepts | Engineering Interview Kit

Concept

Recursion is a programming technique where a function calls itself to solve a smaller instance of the exact same problem.

Imagine standing in a line of 100 people, and you want to know what position you are in.

Iterative approach: You step out of line, walk to the front, and manually count everyone: 1, 2, 3… 100.
Recursive approach: You tap the person in front of you and ask: “What position are you?” They don’t know, so they tap the person in front of them. This continues until the very first person in line is asked. They know they are position 1! They pass 1 back. The next person adds 1 (2) and passes it back. The answer bubbles all the way back to you!

The Two Pillars of Recursion

Every recursive function MUST have two distinct parts. If either is missing, the code will fail catastrophically.

The Base Case: The absolute simplest, trivial version of the problem that can be answered immediately without further recursion. (The person at the very front of the line who says “I am 1!”). This stops the recursion from running infinitely.
The Recursive Step: The part where the function calls itself, mathematically shrinking the problem size (e.g., $N-1$ ) so it eventually hits the Base Case.

Classic Example: Factorial

Factorial of 5 ( $5!$ ) is $5 \times 4 \times 3 \times 2 \times 1$ .
Notice the mathematical pattern: $5! = 5 \times 4!$
Because $4!$ is the exact same problem but slightly smaller, this is a perfect candidate for recursion.

function factorial(n: number): number {
    // 1. The Base Case (Stops infinite loops)
    if (n === 1) {
        return 1;
    }
    
    // 2. The Recursive Step (Shrinks the problem)
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Why use Recursion?

Recursion is rarely used just to do simple math (a for loop is usually faster and safer).
Recursion is strictly used when dealing with Hierarchical Data Structures (Trees and Graphs), or when exploring Multiple Branching Paths (Backtracking/Permutations).

Trying to traverse a Tree or generate Permutations using while loops requires massive amounts of manual state-tracking. Recursion is mathematically elegant because it offloads all of that state-tracking directly to the computer’s CPU (The Call Stack).

Interview Strategy

When you write a recursive function in an interview, you must explicitly vocalize the Two Pillars to the interviewer:
“First, let me write the Base Case so we don’t infinitely loop… Next, I’ll write the Recursive Step, ensuring we pass $N-1$ so we actually make progress towards the Base Case.”

Interview Questions

Q: A developer writes a recursive function to find a target in a Binary Tree, but they forget to return the recursive call: if (node.val < target) { searchTree(node.right); }. What happens?
A: The function will execute successfully, find the target deep in the tree, and return it. But because the developer forgot the return keyword in the middle of the chain, the parent function ignores the child’s answer and implicitly returns undefined. The correct answer is instantly lost in the Call Stack. Every recursive branch must actively pass its findings back up the chain using return.

Q: What is the Time Complexity of calculating Fibonacci recursively: fib(n) = fib(n-1) + fib(n-2)?
A: The time complexity is catastrophic: $O(2^N)$ (Exponential Time). Every single function call branches into 2 more function calls. For fib(50), this triggers over 1 quadrillion function calls, completely freezing the computer. This is why pure recursion must often be optimized using Memoization (Dynamic Programming) to cache the answers and drop the time complexity to $O(N)$ .