Chapter 2 of 6

Stacks

Core Operations

Stack and the LIFO Principle

A stack is a linear data structure where elements are added and removed from only one end, called the top. The rule followed is Last In, First Out (LIFO), which means the element added most recently is the one that gets removed first. Think of a stack of plates on a dining table. You always place a new plate on the top, and you always take a plate from the top. You never take from the bottom or middle.

Example 178: Real World Example of LIFO

Think of a stack of books on a desk. If you place book $A$ first, then book $B$, book $C$, then book $D$ on top, the only book you can pick up right now is book $D$. After removing $D$, you can reach $C$. After removing $C$, you can reach $B$, and finally $A$. This is exactly LIFO.

Core Stack Operations

A stack supports three main operations. All three take constant time, $O(1)$, meaning no matter how many elements are in the stack, these operations always take the same amount of time.

Push(x): Add element $x$ on the top of the stack.
Pop(): Remove and return the element currently on top of the stack.
Peek() / Top(): Look at the element on top, without removing it.

Two more helper operations are usually included.

IsEmpty(): Check if the stack has no elements.
IsFull(): Check if the stack has no more room (only for array-based implementation).

Array Implementation

Stack Using an Array

We can implement a stack using a fixed-size array. We keep a variable called top, which stores the index of the topmost element in the array. Initially, before any element is pushed, top is set to $-1$, which means the stack is empty. When we push an element, we first increase top by $1$, and then store the element at index top. When we pop, we return the element at index top, and then decrease top by $1$.

Example 179: Step by Step: Push and Pop Trace

Suppose we have an empty stack with maximum size $5$. We perform: Push(10), Push(20), Push(30), Pop(), Peek().

Start: top = -1, array = [\_, \_, \_, \_, \_]
Push(10): top = 0, array = [10, \_, \_, \_, \_]
Push(20): top = 1, array = [10, 20, \_, \_, \_]
Push(30): top = 2, array = [10, 20, 30, \_, \_]
Pop(): returns $30$, top = 1, array = [10, 20, \_, \_, \_]
Peek(): returns $20$ (top element), top stays at $1$

Algorithm, Pseudocode and Python Implementation

Example 180: Pseudocode: Full Stack Implementation

Stack Operations (C-style Pseudocode)

Initialize(S, maxsize):
S.arr = array of size maxsize
S.top = -1
S.maxsize = maxsize
Push(S, x):
if S.top == S.maxsize - 1:
print "Stack Overflow"
return
S.top = S.top + 1
S.arr[S.top] = x
Pop(S):
if S.top == -1:
print "Stack Underflow"
return -1
x = S.arr[S.top]
S.top = S.top - 1
return x
Peek(S):
if S.top == -1:
print "Stack is Empty"
return -1
return S.arr[S.top]
IsEmpty(S):
return (S.top == -1)
IsFull(S):
return (S.top == S.maxsize - 1)

stack-array.py

class Stack:
    def __init__(self, maxsize):
        self.arr = [None] * maxsize   # fixed size array
        self.top = -1                  # stack is empty
        self.maxsize = maxsize

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.maxsize - 1

    def push(self, x):
        if self.is_full():
            print("Stack Overflow")   # no space left
            return
        self.top += 1
        self.arr[self.top] = x

    def pop(self):
        if self.is_empty():
            print("Stack Underflow")   # nothing to remove
            return -1
        x = self.arr[self.top]
        self.top -= 1
        return x

    def peek(self):
        if self.is_empty():
            print("Stack is Empty")
            return -1
        return self.arr[self.top]


# --- Driver Code ---
s = Stack(5)

s.push(10)
s.push(20)
s.push(30)

print("Peek:", s.peek())    # Output: 30
print("Pop:", s.pop())      # Output: 30
print("Pop:", s.pop())      # Output: 20
print("Peek:", s.peek())    # Output: 10
print("IsEmpty:", s.is_empty())  # Output: False

Example 181: Why All Operations are $O(1)$

All three main stack operations, Push, Pop, and Peek, take constant time $O(1)$. This is because, in an array-based implementation, each operation only does a fixed number of steps, no loops, no searching. Push increases top by $1$ and stores a value, which is just $2$ steps. Pop reads a value and decreases top by $1$, again just $2$ steps. Peek reads one value, just $1$ step. None of these steps depend on how many elements are in the stack. So, the time stays constant, no matter whether the stack has $1$ element or $1000$ elements.

Example 182: Overflow and Underflow Conditions

Two important error conditions exist for an array-based stack.

Stack Overflow: This happens when we try to push an element into a full stack, that means when top == maxsize - 1. The array has no more room.
Stack Underflow: This happens when we try to pop or peek from an empty stack, that means when top == -1. There is no element to return.

Applications of Stacks

Why Stacks are Useful

Stacks are used in many real problems where the most recently seen item needs to be processed first. The LIFO property makes stacks perfect for expression evaluation, matching symbols, tracking function calls, and converting between expression notations. All these applications rely on the same idea, the last thing we stored is the first thing we need.

Expression Notations: Infix, Postfix, Prefix

Three Notations for Expressions

A mathematical expression like $A + B$ can be written in three different ways, depending on where the operator is placed relative to the operands.

Infix: Operator is between operands. Example: $A + B$. This is the normal way humans write expressions. Requires parentheses and precedence rules to avoid ambiguity.
Postfix (Reverse Polish Notation): Operator comes after operands. Example: $A\;B\;+$. No parentheses needed. Easy for computers to evaluate using a stack.
Prefix (Polish Notation): Operator comes before operands. Example: $+\;A\;B$. Also no parentheses needed.

Infix to Postfix Conversion (Shunting-Yard Algorithm)

Infix to Postfix Conversion

We use a stack to convert an infix expression to postfix. The idea is, we scan the infix expression left to right. Operands (numbers or variables) go directly to the output. Operators are pushed onto the stack, but before pushing, we first pop all operators of higher or equal precedence already in the stack, and send them to output. Opening brackets are pushed onto the stack. Closing brackets trigger popping until we find the matching opening bracket. At the end, all remaining operators in the stack are popped to output.

Operator Precedence Rules

Highest precedence: \^{} (exponentiation), right to left associativity
Medium precedence: * and /, left to right associativity
Lowest precedence: + and -, left to right associativity
Brackets: ( has lowest precedence when inside the stack

Infix to Postfix Conversion (Shunting-Yard Algorithm)

We use an operator stack to convert an infix expression to postfix by scanning the infix tokens from left to right:

Operands (numbers or variables) go directly to the output.
Opening brackets ( are pushed directly onto the stack.
Closing brackets ) trigger popping all operators from the stack to the output until the matching opening bracket ( is found. Discard both brackets.
Operators ($O_1$) trigger popping an operator ($O_2$) from the top of the stack to the output if:
1. $O_2$ has strictly higher precedence than $O_1$, OR
2. $O_2$ has equal precedence to $O_1$ AND $O_1$ is left-associative (e.g., +, -, *, /).
Repeat this check for the new stack top. Stop popping as soon as the condition fails, then push $O_1$ onto the stack. (Note: Right-associative operators like \^{} will not pop an equal-precedence operator).
End of expression: Pop all remaining operators from the stack and send them to the output.

Example 183: Step by Step: Convert $A + B * C - D$ to Postfix

Scan left to right. Stack starts empty, output is empty.

Example 184: Pseudocode: Infix to Postfix

InfixToPostfix(expr)

stack = empty, output = empty list
for each token t in expr:
if t is operand:
append t to output
else if t == '(':
push t onto stack
else if t == ')':
while stack top != '(':
pop and append to output
pop '(' from stack (discard)
else: (t is operator)
while stack not empty and prec(stack top) $>=$ prec(t):
pop and append to output
push t onto stack
while stack not empty:
pop and append to output
return output

infix-to-postfix.py

def infix_to_postfix(expr):
    precedence = {'+': 1, '-': 1,
                  '*': 2, '/': 2,
                  '^': 3}
    stack  = []
    output = []

    for token in expr:
        if token.isalnum():          # operand
            output.append(token)

        elif token == '(':
            stack.append(token)

        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()              # remove '('

        else:                        # operator
            while (stack and
                   stack[-1] != '(' and
                   precedence.get(stack[-1], 0) >= precedence[token]):
                output.append(stack.pop())
            stack.append(token)

    while stack:                     # remaining operators
        output.append(stack.pop())

    return ' '.join(output)


# --- Driver Code ---
expr = ['A', '+', 'B', '*', 'C', '-', 'D']
print(infix_to_postfix(expr))
# Output: A B C * + D -

Postfix Expression Evaluation

Postfix Evaluation Using Stack

Evaluating a postfix expression using a stack is simple. We scan the postfix expression left to right. If the current token is an operand, we push it onto the stack. If the current token is an operator, we pop two operands from the stack, apply the operator, and push the result back. At the end, the stack contains exactly one value, which is the final answer.

Example 185: Step by Step: Evaluate $2\;3\;4\;*\;+\;5\;-$

Expression is already in postfix. Scan left to right.

postfix-eval.py

def evaluate_postfix(expr):
    stack = []

    for token in expr:
        if token.lstrip('-').isdigit():   # operand
            stack.append(int(token))

        else:                              # operator
            b = stack.pop()               # second operand
            a = stack.pop()               # first operand

            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                stack.append(a // b)

    return stack[0]   # final result


# --- Driver Code ---
expr = ['2', '3', '4', '*', '+', '5', '-']
print("Result:", evaluate_postfix(expr))
# Output: Result: 9

Infix to Prefix Conversion

Converting infix to prefix uses a similar idea as infix to postfix, but with two key differences. First, we reverse the entire infix expression and swap each ( with ) and vice versa. Second, when running the Shunting-Yard algorithm on this modified expression, we invert the equal precedence rule:

Strictly Higher Precedence on Stack: Pop operators from stack to output.
Strictly Lower Precedence on Stack: Push the incoming operator onto the stack.
Equal Precedence (Associativity Rule):
- For left-associative operators (+, -, *, /): Push onto the stack (do not pop).
- For right-associative operators (\^{}): Pop the stack top to output before pushing.

At the end, we reverse the final output string to obtain the prefix expression.

Example 186: Step by Step: Convert $A + B * C$ to Prefix

Step 1: Reverse the expression: $C * B + A$

Step 2: No brackets in this example, so no swapping needed.

Step 3: Apply modified Shunting-Yard on $C * B + A$:

$C$ $\to$ output: $C$
$*$ $\to$ stack: $[*]$
$B$ $\to$ output: $C\;B$
$+$ $\to$ stack top $*$ has strictly higher precedence than $+$, so pop $*$ to output, push $+ \to$ output: $C\;B\;*$
$A$ $\to$ output: $C\;B\;*\;A$
End $\to$ pop $+ \to$ output: $C\;B\;*\;A\;+$

Step 4: Reverse: $+\;A\;*\;B\;C$

Final Prefix: $+\;A\;*\;B\;C$, which is same as $A + (B * C)$.

“`

infix-to-prefix.py

def infix_to_postfix_helper(expr):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack  = []
    output = []

    for token in expr:
        if token.isalnum():
            output.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()
        else:
            while (stack and
                   stack[-1] != '(' and
                   precedence.get(stack[-1], 0) >= precedence[token]):
                output.append(stack.pop())
            stack.append(token)

    while stack:
        output.append(stack.pop())

    return output


def infix_to_prefix(expr):
    # Step 1: Reverse
    rev = expr[::-1]

    # Step 2: Swap brackets
    swapped = []
    for token in rev:
        if token == '(':
            swapped.append(')')
        elif token == ')':
            swapped.append('(')
        else:
            swapped.append(token)

    # Step 3: Apply postfix conversion
    postfix = infix_to_postfix_helper(swapped)

    # Step 4: Reverse result
    prefix = postfix[::-1]

    return ' '.join(prefix)


# --- Driver Code ---
expr = ['A', '+', 'B', '*', 'C']
print(infix_to_prefix(expr))
# Output: + A * B C

Prefix Expression Evaluation

Prefix Expression Evaluation Rules

To evaluate a prefix expression using a stack:

Scan the prefix expression from right to left.
If the symbol is an operand (number), push it onto the stack.
If the symbol is an operator, pop two elements from the stack:
- $Op_1 = \text{first popped}$
- $Op_2 = \text{second popped}$
Compute $\text{result} = Op_1 \ \text{operator} \ Op_2$ and push the result back onto the stack.
The final stack value is the expression's result.

Example 187: Step-by-Step: Evaluate Prefix Expression 1

Expression: $- \ * \ 4 \ 3 \ / \ 8 \ 2$

Scan right to left:
Push $2$, Push $8 \to \text{Stack: } [2, 8]$
Read $/ \to \text{Pop } Op_1=8, Op_2=2 \implies 8 / 2 = 4 \to \text{Stack: } [4]$
Push $3$, Push $4 \to \text{Stack: } [4, 3, 4]$
Read $* \to \text{Pop } Op_1=4, Op_2=3 \implies 4 * 3 = 12 \to \text{Stack: } [4, 12]$
Read $- \to \text{Pop } Op_1=12, Op_2=4 \implies 12 - 4 = 8 \to \text{Stack: } [8]$

Final Result: $8$

Example 188: Step-by-Step: Evaluate Prefix Expression 2

Expression: $+ \ * \ 2 \ 5 \ \hat{} \ 3 \ 2$

Scan right to left:
Push $2$, Push $3 \to \text{Stack: } [2, 3]$
Read $\hat{} \to \text{Pop } Op_1=3, Op_2=2 \implies 3^2 = 9 \to \text{Stack: } [9]$
Push $5$, Push $2 \to \text{Stack: } [9, 5, 2]$
Read $* \to \text{Pop } Op_1=2, Op_2=5 \implies 2 * 5 = 10 \to \text{Stack: } [9, 10]$
Read $+ \to \text{Pop } Op_1=10, Op_2=9 \implies 10 + 9 = 19 \to \text{Stack: } [19]$

Final Result: $19$

Prefix to Infix Conversion

How to Convert Prefix to Infix

Scan the prefix expression from right to left.
If the current token is an operand, push it onto the stack as-is.
If the current token is an operator, pop two values: call the first popped value $A$ and the second popped value $B$. Form the string $(A \ \text{op} \ B)$ and push this back onto the stack.
After the scan ends, the stack contains exactly one string — this is the fully bracketed infix expression.

Example 189: Step-by-Step: Convert $+ \ * \ A \ B \ / \ C \ D$ to Infix

Scan right to left:
Push $D, C \to \text{Stack: } [D, C]$
Read $/ \to \text{Pop } A=C, B=D \implies \text{Push } (C / D) \to \text{Stack: } [(C / D)]$
Push $B, A \to \text{Stack: } [(C / D), B, A]$
Read $* \to \text{Pop } A=A, B=B \implies \text{Push } (A * B) \to \text{Stack: } [(C / D), (A * B)]$
Read $+ \to \text{Pop } A=(A * B), B=(C / D) \implies \text{Push } ((A * B) + (C / D))$

Final Infix: $(A * B) + (C / D)$

Example 190: Step-by-Step: Convert $- \ + \ A \ * \ B \ C \ \hat{} \ D \ E$ to Infix

Scan right to left:
Push $E, D \to \text{Stack: } [E, D]$
Read $\hat{} \to \text{Pop } A=D, B=E \implies \text{Push } (D \hat{} E) \to \text{Stack: } [(D \hat{} E)]$
Push $C, B \to \text{Stack: } [(D \hat{} E), C, B]$
Read $* \to \text{Pop } A=B, B=C \implies \text{Push } (B * C) \to \text{Stack: } [(D \hat{} E), (B * C)]$
Push $A \to \text{Stack: } [(D \hat{} E), (B * C), A]$
Read $+ \to \text{Pop } A=A, B=(B * C) \implies \text{Push } (A + (B * C)) \to \text{Stack: } [(D \hat{} E), (A + (B * C))]$
Read $- \to \text{Pop } A=(A + (B * C)), B=(D \hat{} E) \implies \text{Push } ((A + (B * C)) - (D \hat{} E))$

Final Infix: $((A + (B * C)) - (D \hat{} E))$

Postfix to Prefix Conversion

How to Convert Postfix to Prefix

Scan the postfix expression from left to right.
If the current token is an operand, push it onto the stack as-is.
If the current token is an operator, pop two values: call the first popped value $B$ and the second popped value $A$. Form the string $\text{op} \ A \ B$ (operator written first) and push this back onto the stack.
After the scan ends, the stack contains exactly one string — this is the prefix expression.

Example 191: Step-by-Step: Convert $A \ B \ + \ C \ D \ - \ *$ to Prefix

Scan left to right:
Push $A, B \to \text{Stack: } [A, B]$
Read $+ \to \text{Pop } B=B, A=A \implies \text{Push } + A B \to \text{Stack: } [+ A B]$
Push $C, D \to \text{Stack: } [+ A B, C, D]$
Read $- \to \text{Pop } B=D, A=C \implies \text{Push } - C D \to \text{Stack: } [+ A B, - C D]$
Read $* \to \text{Pop } B=- C D, A=+ A B \implies \text{Push } * + A B - C D$

Final Prefix: $* \ + \ A \ B \ - \ C \ D$

Example 192: Step-by-Step: Convert $A \ B \ C \ * \ + \ D \ E \ F \ - \ / \ -$ to Prefix

Scan left to right:
Push $A, B, C \to \text{Stack: } [A, B, C]$
Read $* \to \text{Pop } B=C, A=B \implies \text{Push } * B C \to \text{Stack: } [A, * B C]$
Read $+ \to \text{Pop } B=* B C, A=A \implies \text{Push } + A * B C \to \text{Stack: } [+ A * B C]$
Push $D, E, F \to \text{Stack: } [+ A * B C, D, E, F]$
Read $- \to \text{Pop } B=F, A=E \implies \text{Push } - E F \to \text{Stack: } [+ A * B C, D, - E F]$
Read $/ \to \text{Pop } B=- E F, A=D \implies \text{Push } / D - E F \to \text{Stack: } [+ A * B C, / D - E F]$
Read $- \to \text{Pop } B=/ D - E F, A=+ A * B C \implies \text{Push } - + A * B C / D - E F$

Final Prefix: $- \ + \ A \ * \ B \ C \ / \ D \ - \ E \ F$

Prefix to Postfix Conversion

How to Convert Prefix to Postfix

Scan the prefix expression from right to left.
If the current token is an operand, push it onto the stack as-is.
If the current token is an operator, pop two values: call the first popped value $A$ and the second popped value $B$. Form the string $A \ B \ \text{op}$ (operator written last) and push this back onto the stack.
After the scan ends, the stack contains exactly one string — this is the postfix expression.

Example 193: Step-by-Step: Convert $* \ + \ A \ B \ - \ C \ D$ to Postfix

Scan right to left:
Push $D, C \to \text{Stack: } [D, C]$
Read $- \to \text{Pop } A=C, B=D \implies \text{Push } C D - \to \text{Stack: } [C D -]$
Push $B, A \to \text{Stack: } [C D -, B, A]$
Read $+ \to \text{Pop } A=A, B=B \implies \text{Push } A B + \to \text{Stack: } [C D -, A B +]$
Read $* \to \text{Pop } A=A B +, B=C D - \implies \text{Push } A B + C D - *$

Final Postfix: $A \ B \ + \ C \ D \ - \ *$

Example 194: Step-by-Step: Convert $- \ / \ * \ A \ B \ C \ + \ D \ E$ to Postfix

Scan right to left:
Push $E, D \to \text{Stack: } [E, D]$
Read $+ \to \text{Pop } A=D, B=E \implies \text{Push } D E + \to \text{Stack: } [D E +]$
Push $C, B, A \to \text{Stack: } [D E +, C, B, A]$
Read $* \to \text{Pop } A=A, B=B \implies \text{Push } A B * \to \text{Stack: } [D E +, C, A B *]$
Read $/ \to \text{Pop } A=A B *, B=C \implies \text{Push } A B * C / \to \text{Stack: } [D E +, A B * C /]$
Read $- \to \text{Pop } A=A B * C /, B=D E + \implies \text{Push } A B * C / D E + -$

Final Postfix: $A \ B \ * \ C \ / \ D \ E \ + \ -$

Balanced Parentheses / Brackets Check

Balanced Brackets Check

A string of brackets is balanced if every opening bracket has a corresponding closing bracket, in the correct order, and no closing bracket appears before its matching opening bracket. We use a stack to check this. We scan the string left to right. For every opening bracket (, [, or {, we push it onto the stack. For every closing bracket, we check if the top of the stack has the matching opening bracket. If yes, we pop it. If no, the string is not balanced. At the end, if the stack is empty, the string is balanced.

Example 195: Tracing Balanced Check on $\{[A+B]*(C-D)\}$

Each character is scanned left to right.

balanced-brackets.py

def is_balanced(expr):
    stack   = []
    opening = {'(', '[', '{'}
    closing = {')': '(', ']': '[', '}': '{'}

    for ch in expr:
        if ch in opening:
            stack.append(ch)          # push opener

        elif ch in closing:
            if not stack:
                return False          # no opener to match
            top = stack.pop()
            if top != closing[ch]:    # wrong match
                return False

    return len(stack) == 0            # must be empty at end


# --- Driver Code ---
tests = [
    "{[A+B]*(C-D)}",
    "((A+B)",
    "{[A+B)}",
    "(A+(B*C))"
]

for t in tests:
    result = "Balanced" if is_balanced(t) else "NOT Balanced"
    print(f"{t:20s} -> {result}")

# Output:
# {[A+B]*(C-D)}       -> Balanced
# ((A+B)              -> NOT Balanced
# {[A+B)}             -> NOT Balanced
# (A+(B*C))           -> Balanced

Recursion and Call Stack Frames

How Recursion Uses the Call Stack

Every time a function calls itself (or calls another function), the computer needs to remember where to come back, what local variables were in use, and what the current values were. For this, the computer uses a special stack, called the call stack. Each time a function is called, a block of memory called a stack frame (or activation record) is pushed onto the call stack. This frame stores the local variables, parameters, and the return address. When the function finishes, its frame is popped off the call stack, and control returns to the previous frame.

Example 196: What a Stack Frame Contains

Each time a function is called, the system pushes a frame that stores:

The function's local variables and parameters
The return address (where to go after this function finishes)
The return value (what the function should give back to the caller)

Example 197: Tracing Call Stack for factorial(3)

Calls going DOWN (pushing frames):

factorial(3) is called $\to$ pushes frame, calls factorial(2)
factorial(2) is called $\to$ pushes frame, calls factorial(1)
factorial(1) is called $\to$ pushes frame, calls factorial(0)
factorial(0) is called $\to$ pushes frame, hits base case, returns $1$

Returns going UP (popping frames):

factorial(0) returns $1$ $\to$ frame popped
factorial(1) gets $1$, returns $1 \times 1 = 1$ $\to$ frame popped
factorial(2) gets $1$, returns $2 \times 1 = 2$ $\to$ frame popped
factorial(3) gets $2$, returns $3 \times 2 = 6$ $\to$ frame popped

Example 198: Pseudocode: Recursion with Frame Concept

Factorial(n):

Push frame: store n, return address
if n == 0:
result = 1
else:
result = n * Factorial(n-1) // new frame pushed here
Pop frame: send result back to caller
return result

recursion-call-stack.py

import sys

def factorial(n, depth=0):
    indent = "  " * depth
    print(f"{indent}factorial({n}) called"
          f"  [stack depth = {depth}]")

    if n == 0:
        print(f"{indent}factorial(0) returns 1  [BASE CASE]")
        return 1

    result = n * factorial(n - 1, depth + 1)

    print(f"{indent}factorial({n}) returns {result}"
          f"  [frame popped]")
    return result


# --- Driver Code ---
print("=" * 50)
ans = factorial(4)
print("=" * 50)
print("Final Answer:", ans)

# Output (abbreviated):
# factorial(4) called  [stack depth = 0]
#   factorial(3) called  [stack depth = 1]
#     factorial(2) called  [stack depth = 2]
#       factorial(1) called  [stack depth = 3]
#         factorial(0) called  [stack depth = 4]
#         factorial(0) returns 1  [BASE CASE]
#       factorial(1) returns 1  [frame popped]
#     factorial(2) returns 2  [frame popped]
#   factorial(3) returns 6  [frame popped]
# factorial(4) returns 24  [frame popped]
# Final Answer: 24

Stack Overflow Due to Deep Recursion

Since each recursive call pushes a new frame onto the call stack, very deep recursion can fill up all available stack space. When the call stack runs out of space, a Stack Overflow error occurs. This is why recursive functions must always have a base case that stops recursion, and why the recursion depth matters in practice. In Python, the default recursion depth limit is around $1000$ calls.