📊 We use cookies & analytics to improve your experience. Learn more
Latest

Interview DSA Crash Course Module 3 · Lesson 8 of 15

0% Exit to course

Module 3 · Recursion, trees and the questions you cannot prepare for Lesson 8 of 15

Recursion and the call stack

Learning objective

A recursive function calls itself on a smaller input. Every recursion needs a base case or it never stops — the single most common failure in a live interview.

The concept

A recursive function calls itself on a smaller version of the problem, with a base case that stops. Factorial, the sum of a list, a tree walk and binary search all have the same three parts: the base case, the smaller call, and what you do with the result. Every call sits on the stack until the innermost one returns.

The useful skill is converting between the two. Every recursive function can be written with an explicit stack or a loop, and interviewers ask for it when recursion depth would overflow. Practise factorial and Fibonacci both ways — it is the same reasoning applied twice and it comes up constantly.

Python
def factorial(n):
    if n <= 1:                 # base case - stops the recursion
        return 1
    return n * factorial(n - 1)

# The same thing with a loop
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# A base case that never triggers -> RecursionError. Print n to debug.

Common mistakes

The mistake is a base case that never triggers: if n == 0 when n can go negative, or a recursive call with the same argument. If you see a recursion error, print n on each call and the missing step is almost always visible in three lines of output.

Worked example

factorial(n) = n * factorial(n - 1) with factorial(0) = 1 is complete; omit the base case and the answer is a stack overflow in front of the interviewer.

Your practice task

Write three recursive solutions by hand, each with the base case written FIRST, then verify on paper for n = 0 and n = 1.

Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.

Key takeaway

A recursive function calls itself on a smaller version of the problem, with a base case that stops.

Create free account or sign in

Almost there

15 lessons left of 15

Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.