Recursion

DSA · Introduction to DSA

Theory

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case that stops the calls and a recursive case that moves towards the base case. Each call is placed on the call stack until it returns, so deep recursion uses O(depth) memory. Many structures, such as trees and nested folders, are naturally recursive.

Why we use it

Recursion expresses divide-and-conquer, tree traversal and backtracking very clearly, often in a few lines where a loop would need an explicit stack.

When to use it

Use recursion for trees, graphs (DFS), divide and conquer (merge sort, quick sort), backtracking and problems defined in terms of smaller sub-problems. Prefer loops when depth could be very large, because Python limits recursion depth to about 1000.

How it works

  1. Call f(n)
  2. Is n a base case? Yes: Return the base value. No: Call f(smaller n).
  3. Wait for the smaller call to return
  4. Combine its result with the current step
  5. Return the result to the caller

Syntax

def solve(problem):
    if problem is small enough:   # base case
        return direct answer
    smaller = shrink(problem)     # recursive case
    return combine(solve(smaller))

Example

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

def sum_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

print("5! =", factorial(5))
print("Sum of digits of 98765 =", sum_digits(98765))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic