Recursion Concept and Call Stack Visualization in DSA Python

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case.

Analogy: Imagine a set of Russian dolls where each doll contains a smaller doll inside until the smallest doll is reached and then you open them back up in reverse order.

function call stack:
main()
  ↓
recursive_function(n)
  ↓
recursive_function(n-1)
  ↓
...
  ↓
recursive_function(base_case)
  ↑
return from base_case
  ↑
return from recursive_function(n-1)
  ↑
return from recursive_function(n)
  ↑
back to main()

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursive calls build up and then return results step-by-step

Step 1: Call factorial(3), which calls factorial(2)

call stack: factorial(3) -> factorial(2)

Why: We break the problem into smaller parts by calling factorial with smaller number

Step 2: factorial(2) calls factorial(1)

call stack: factorial(3) -> factorial(2) -> factorial(1)

Why: Keep breaking down until we reach the simplest case

Step 3: factorial(1) calls factorial(0), the base case

call stack: factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

Why: Base case stops recursion to prevent infinite calls

Step 4: factorial(0) returns 1 (base case result)

returning: factorial(0) = 1

Why: Base case provides a known answer to build upon

Step 5: factorial(1) returns 1 * factorial(0) = 1 * 1 = 1

returning: factorial(1) = 1

Why: Combine current number with result from smaller problem

Step 6: factorial(2) returns 2 * factorial(1) = 2 * 1 = 2

returning: factorial(2) = 2

Why: Build result step by step going back up the call stack

Step 7: factorial(3) returns 3 * factorial(2) = 3 * 2 = 6

returning: factorial(3) = 6

Why: Final answer is computed after all recursive calls return

Result:

call stack empty
final result: factorial(3) = 6

Annotated Code

DSA Python

def factorial(n: int) -> int:
    # base case: stop recursion when n is 0
    if n == 0:
        return 1
    # recursive case: multiply n by factorial of n-1
    return n * factorial(n - 1)

# driver code
result = factorial(3)
print(f"factorial(3) = {result}")

if n == 0:

check for base case to stop recursion

return 1

return base case result

return n * factorial(n - 1)

recursive call to solve smaller problem and combine result

Output

factorial(3) = 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) because each recursive call adds a layer to the call stack

vs Alternative: Iterative approach uses O(1) space but recursion is easier to write and understand for problems naturally defined by smaller subproblems

Edge Cases

n = 0 (base case)

Returns 1 immediately without further calls

DSA Python

if n == 0:

n = 1

Calls factorial(0) once then returns 1

DSA Python

return n * factorial(n - 1)

negative n

No guard in code, leads to infinite recursion and crash

DSA Python

No explicit guard; user must input non-negative integers

When to Use This Pattern

When you see a problem that can be broken down into smaller similar problems, think of recursion because it naturally solves by calling itself with simpler inputs.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and program crash
Fix: Always include a base case that stops recursion

Mistake: Not reducing the problem size in recursive call leads to infinite recursion
Fix: Make sure each recursive call uses a smaller input closer to the base case

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple base case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems.

The key is the base case that stops recursion and the call stack that remembers each step until results combine.

Practice

1. What does recursion mean in programming?
def recurse():
recurse()


easy

A. A function calling itself to solve smaller parts of a problem

B. A loop that runs forever

C. A function that never ends

D. A way to store data in a list

Solution

1. Step 1: Understand recursion definition

   Recursion is when a function calls itself to break down a problem into smaller parts.

2. Step 2: Match with options

   A function calling itself to solve smaller parts of a problem correctly describes recursion as self-calling function for smaller problems.

3. Final Answer:

   A function calling itself to solve smaller parts of a problem -> Option A

4. Quick Check:

   Recursion = self-calling function [OK]

Hint: Recursion means function calls itself to solve smaller parts [OK]

Common Mistakes:

• Confusing recursion with infinite loops
• Thinking recursion is just a loop
• Believing recursion stores data like lists

2. Which of the following is the correct syntax to define a recursive function in Python?

easy

A. def recurse(): recurse()

B. def recurse(): return recurse()

C. def recurse(): recurse() return

D. def recurse(): print('recurse')

Solution

1. Step 1: Check function syntax for recursion

   A recursive function must call itself. It does not always require a return statement unless the return value is used.

2. Step 2: Analyze options

   def recurse(): recurse() correctly defines a recursive function that calls itself.

3. Final Answer:

   def recurse(): recurse() -> Option A

4. Quick Check:

   Recursive call without return is valid syntax [OK]

Hint: Recursive function must call itself; return is optional if return value unused [OK]

Common Mistakes:

• Missing recursive call
• Incorrect use of return
• Confusing print statement with recursion

3. What is the output of this code?

def countdown(n):
    if n == 0:
        return 'Done'
    else:
        print(n)
        return countdown(n-1)

countdown(3)

medium

A. Done

B. 3 2 1 Done

C. 3 2 1

D. 1 2 3 Done

Solution

1. Step 1: Trace recursive calls and prints

   Function prints n then calls countdown(n-1) until n=0, then returns 'Done'. So prints 3, 2, 1 in order.

2. Step 2: Understand return value and print output

   Only numbers 3, 2, 1 are printed. 'Done' is returned but not printed, so output shows numbers only.

3. Final Answer:

   3 2 1 -> Option C

4. Quick Check:

   Prints countdown down to 1 then returns 'Done' [OK]

Hint: Print happens before recursive call, so numbers print descending [OK]

Common Mistakes:

• Thinking 'Done' is printed automatically
• Confusing order of printed numbers
• Ignoring base case return

4. Find the error in this recursive function:

def sum_to_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_to_n(n)

print(sum_to_n(3))

medium

A. Missing base case

B. Recursive call uses n instead of n-1

C. Function does not return anything

D. Syntax error in function definition

Solution

1. Step 1: Check recursive call parameter

   Recursive call should reduce n by 1 to approach base case, but it calls sum_to_n(n) again causing infinite recursion.

2. Step 2: Identify correct fix

   Change recursive call to sum_to_n(n-1) to reduce n each time and reach base case.

3. Final Answer:

   Recursive call uses n instead of n-1 -> Option B

4. Quick Check:

   Recursive call must reduce n to avoid infinite loop [OK]

Hint: Recursive call must move toward base case by changing argument [OK]

Common Mistakes:

• Calling function with same argument causing infinite recursion
• Forgetting to reduce argument in recursion
• Confusing base case presence

5. Given this recursive function to calculate factorial:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

What is the call stack sequence when calling factorial(3)?

hard

A. factorial(1) -> factorial(2) -> factorial(3)

B. factorial(0) -> factorial(1) -> factorial(2) -> factorial(3)

C. factorial(3) -> factorial(3) -> factorial(3)

D. factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

Solution

1. Step 1: Understand recursive calls order

   factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0) base case.

2. Step 2: Trace call stack sequence

   Calls go down from 3 to 0 before returning results back up the stack.

3. Final Answer:

   factorial(3) -> factorial(2) -> factorial(1) -> factorial(0) -> Option D

4. Quick Check:

   Recursive calls descend to base case 0 [OK]

Hint: Recursive calls go down to base case before returning [OK]

Common Mistakes:

• Thinking calls go from base case up
• Repeating same call multiple times
• Skipping base case call