A stack is called a recursive data structure because it naturally supports and mimics recursion in how it operates and stores data.

Recursion:

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

Stack:

A stack is a Last In, First Out (LIFO) data structure.

- Push elements onto it (add to the top).

- Pop elements from it (remove from the top).

How Stack Supports Recursion When a function calls itself:

- The system must pause the current function and store its state (local variables, return address).

- This is done using a call stack.

- Each recursive call gets pushed onto the stack.

- Once the base case is reached, the calls are popped off the stack one by one, and results are returned.

Example: Factorial using Recursion and Stack

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
Internally:
factorial(3)
=> 3 * factorial(2)
       => 2 * factorial(1)
              => 1 * factorial(0)
                     => returns 1 (base case)
At each step:
    • The current call is pushed onto the stack.
    • When factorial(0) is reached, each call is popped and evaluated:
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

Why Stack is Recursive

- A stack holds information about active function calls.

- Each recursive call adds a new layer (like stacking plates).

- When the base case is reached, the stack unwinds (like popping plates off).

- Recursion wouldn’t work without a stack to track and manage function calls.