Recursion Concept and Call Stack Visualization in DSA Python - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Call function with input n

↓

Check base case: n == 0?

Yes→Return base value

No↓

Call function recursively with n-1

↓

Wait for recursive call result

↓

Process result and return

↓

Return to previous call

↩Back to Check base case

Shows how a recursive function calls itself until a base case is met, then returns back through the call stack.

Execution Sample

DSA Python

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

print(factorial(3))

Calculates factorial of 3 using recursion, showing each call and return.

Execution Table

Step	Operation	Current n	Call Stack Depth	Return Value	Call Stack Visual
1	Call factorial(3)	3	1	?	factorial(3)
2	Call factorial(2)	2	2	?	factorial(3) -> factorial(2)
3	Call factorial(1)	1	3	?	factorial(3) -> factorial(2) -> factorial(1)
4	Call factorial(0)	0	4	?	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
5	Base case reached, return 1	0	4	1	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
6	Return from factorial(1), compute 1 * 1	1	3	1	factorial(3) -> factorial(2) -> factorial(1)
7	Return from factorial(2), compute 2 * 1	2	2	2	factorial(3) -> factorial(2)
8	Return from factorial(3), compute 3 * 2	3	1	6	factorial(3)
9	Return from factorial(3), final result	3	0	6

💡 Recursion ends when base case n==0 is reached and all calls return their computed values.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
n	3	3	2	1	0	0	1	2	3	3
Call Stack Depth	0	1	2	3	4	4	3	2	1	0
Return Value	?	?	?	?	1	1	2	6	6	6

Key Moments - 3 Insights

Why does the function keep calling itself instead of returning immediately?

Because the base case (n == 0) is not met yet, so each call waits for the result of factorial(n-1) before it can return (see steps 1-4 in execution_table).

What happens when the base case is reached?

The function returns 1 immediately (step 5), which starts the process of returning back through the call stack, resolving each waiting call.

How does the call stack depth change during recursion?

It increases by 1 with each recursive call (steps 1-4), then decreases by 1 as each call returns (steps 5-9), shown clearly in the Call Stack Depth column.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the call stack depth?

A 2

B 3

C 4

D 1

💡 Hint

Check the 'Call Stack Depth' column at Step 4 in the execution_table.

At which step does the function reach the base case and return 1?

A Step 5

B Step 3

C Step 7

D Step 9

💡 Hint

Look for the step where 'Base case reached' and return value is 1 in the execution_table.

If we call factorial(4) instead of factorial(3), how would the call stack depth change at the deepest call?

A It would be 3

B It would be 5

C It would be 4

D It would be 6

💡 Hint

Call stack depth equals n+1 at the deepest call; see how factorial(3) has depth 4 at Step 4.

Concept Snapshot

Recursion calls a function within itself until a base case is met.
Each call waits for the next call's result.
Call stack grows with each call and shrinks on return.
Base case stops recursion and starts returning values.
Useful for problems like factorial, Fibonacci, tree traversal.

Full Transcript

Recursion is a method where a function calls itself to solve smaller parts of a problem. The process continues until a base case is reached, which stops further calls. Each recursive call is added to the call stack, which keeps track of active calls. When the base case returns a value, each previous call uses that value to compute its own result and returns it, unwinding the stack. This example shows factorial calculation for 3, where factorial(3) calls factorial(2), which calls factorial(1), and so on until factorial(0) returns 1. Then the results multiply back up to give the final answer 6.

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