Graphic Representation (Visualization) of DSA using Python: Recursion

Follow me

Recursion in Data Structures & Algorithms (Python)

Recursion is a programming technique where a function calls itself to solve a problem.

Instead of solving the entire problem at once, recursion breaks a big problem into smaller sub-problems of the same type, solves them, and combines the results.

What is Recursion?

Recursion is a technique in which:

• A function calls itself

• The problem is reduced step by step

• The process continues until a stopping condition is reached

It works like repeatedly solving smaller versions of the same problem until the simplest case is solved.

Real-World Mental Models of Recursion

1. Nested Doll Model

Each doll contains a smaller doll inside it.

You keep opening dolls until you reach the smallest one.

This is similar to recursion where each function call goes deeper until the base case is reached.

2. Folder Structure Model

A folder can contain sub-folders, and each sub-folder can contain more folders.

To explore all files, the same logic is applied at every level — this is recursion in real life.

The Two Pillars of Recursion

1. Base Case (STOP)

• The condition where recursion ends

• Prevents infinite calls

• Returns a simple, direct result

Without a base case, recursion will never stop and the program will crash.

2. Recursive Case (GO)

• The part where the function calls itself

• Input is reduced or moved closer to the base case

• Ensures progress toward stopping

Both are mandatory for correct recursion.

Anatomy of a Recursive Function

A recursive function has two main parts:

1. Base Case – handles the simplest input

2. Recursive Call – calls the same function with a smaller input

The function keeps calling itself until the base case condition is satisfied.

How Recursion Works Internally: The Call Stack

• Each function call is stored in memory as a stack frame

• Calls follow LIFO (Last In, First Out) order

• New calls are added on top of the stack

• When the base case is reached, calls return one by one

This stack mechanism is why recursion consumes extra memory.

Tracing the Flow: Print 1 to N

• Calls go downward first (winding phase)

• Base case is reached

• Outputs happen while returning (unwinding phase)

Understanding this flow is key to mastering recursion.

Linear Recursion: Factorial (Short)

Factorial means multiplying a number with all numbers below it till 1.

Formula:

n! = n × (n−1) × (n−2) × … × 1

In linear recursion:

• The function makes only one recursive call

• Each call depends on the next call

• Calls form a straight chain

Example idea:

factorial(n) = n × factorial(n−1)

Stops when n = 1 (base case)

✔ One call at a time

✔ No branching

✔ Stack grows linearly

That’s why factorial is called linear recursion.

Branching Recursion: Fibonacci Series

• Each call makes two recursive calls

• Creates a tree-like structure

• Same sub-problems are solved multiple times

• Time complexity grows very fast (exponential)

This shows why optimization is important in recursion.

Types of Recursion

Direct Recursion

A function directly calls itself.

Indirect Recursion

Two or more functions call each other in a cycle.

Tail Recursion

The recursive call is the last statement in the function.

More memory efficient.

Head Recursion

The recursive call happens before processing other statements.

Recursion vs Iteration (Loops)

Recursion

• Cleaner and elegant logic

• Uses call stack (more memory)

• Slower in many cases

• Best for trees, graphs, divide & conquer

Iteration

• Uses loops

• Less memory usage

• Faster execution

• Best for simple repetitions

Trade-off: readability vs performance.

The Danger Zone: Stack Overflow

Occurs when:

• Base case is missing

• Recursive call does not move toward base case

• Input size is too large

In Python, recursion depth is limited (~1000 calls).

Time & Space Complexity in Recursion

Time Complexity

Depends on number of recursive calls.

Branching recursion can become exponential.

Space Complexity

Depends on recursion depth due to call stack.

Usually linear (O(n)).

Optimization

Dynamic Programming / Memoization reduces repeated calculations.

When to Use and Avoid Recursion

Use Recursion When:

• Working with trees and graphs (DFS)

• Using divide & conquer algorithms

• Solving backtracking problems

• Problem is naturally self-similar

Avoid Recursion When:

• Memory is limited

• Performance is critical

• Problem is a simple loop

• Input size is very large

Key Takeaways

• Recursion is a function calling itself

• Must always have Base Case + Recursive Case

• Uses call stack (LIFO)

• Cleaner code for complex structures

• Risk of stack overflow if not handled carefully