Recursion Base Case and Recursive Case in DSA Python - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start Recursive Function

↓

Check Base Case Condition?

↓

Return Base Value

↓

Receive Result from Recursive Call

↓

Process Result and Return

↓

End

The function checks if it reached the simplest case (base case). If yes, it returns a value. Otherwise, it calls itself with a smaller input and processes the result.

Execution Sample

DSA Python

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

Calculates factorial of n using recursion with a base case at n=0.

Execution Table

Step	Call Stack	Current n	Base Case?	Action	Return Value	Visual Call Stack
1	factorial(3)	3	No	Call factorial(2)		factorial(3)
2	factorial(3) -> factorial(2)	2	No	Call factorial(1)		factorial(3) -> factorial(2)
3	factorial(3) -> factorial(2) -> factorial(1)	1	No	Call factorial(0)		factorial(3) -> factorial(2) -> factorial(1)
4	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	0	Yes	Return 1	1	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
5	factorial(3) -> factorial(2) -> factorial(1)	1	No	Return 1 * 1 = 1	1	factorial(3) -> factorial(2) -> factorial(1)
6	factorial(3) -> factorial(2)	2	No	Return 2 * 1 = 2	2	factorial(3) -> factorial(2)
7	factorial(3)	3	No	Return 3 * 2 = 6	6	factorial(3)
8				End recursion	6

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

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	Final
n	3	2	1	0	1	2	3
Return Value					1	1	2	6	6
Call Stack Depth	1	2	3	4	3	2	1	0	0

Key Moments - 3 Insights

Why does the recursion stop at n == 0?

Because the base case condition 'n == 0' returns a value without further recursive calls, stopping infinite recursion as shown in step 4 of the execution_table.

What happens when the function calls itself with n-1?

It creates a new call on the call stack with a smaller input, delaying the return until the base case is reached, as seen in steps 1 to 3 where calls go deeper.

How is the final result computed from recursive calls?

Each call waits for the return value of the next call, then multiplies it by n before returning, shown in steps 5 to 7 where results are combined back up.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value when n is 0?

A 1

B 0

C n

D Undefined

💡 Hint

Check the 'Return Value' column at step 4 where n == 0.

At which step does the recursion start returning values back up the call stack?

A Step 3

B Step 5

C Step 4

D Step 7

💡 Hint

Look for the first step where 'Return Value' is filled and action shows returning a computed value.

If the base case was changed to 'n == 1', how would the execution_table change?

A The return value at n=0 would be 1

B The recursion would never stop

C The recursion would stop one step earlier, base case reached at n=1

D No change in recursion steps

💡 Hint

Think about when the base case condition is true and how it affects call depth.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion by returning a value (e.g., if n == 0: return 1)
- Recursive Case: calls itself with smaller input (e.g., return n * factorial(n-1))
Each call waits for the next call's result before returning.
Without base case, recursion never ends.

Full Transcript

Recursion works by a function calling itself with smaller inputs until it reaches a base case. The base case is a simple condition that stops further calls and returns a value. For example, factorial(0) returns 1. When the base case is reached, the function returns values back up the call stack, combining results at each step. This process is shown step-by-step in the execution table, where calls go deeper until n is 0, then return values multiply back up to compute factorial(3) = 6.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To stop the recursion and prevent infinite calls

B. To call the function again with a smaller input

C. To increase the input size for the next call

D. To print the result of the recursion

Solution

1. Step 1: Understand recursion basics

   Recursion works by calling itself repeatedly until a stopping condition is met.

2. Step 2: Identify the role of base case

   The base case stops further recursive calls to avoid infinite loops.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option A

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid infinite loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls recursion again
• Ignoring the need for a stopping condition

2. Which of the following is the correct syntax for a recursive function in Python that calculates factorial?

easy

A. def fact(n): return n * fact(n+1)

B. def fact(n): while n > 0: return n * fact(n-1)

C. def fact(n): if n == 1: return 0 else: return n + fact(n-1)

D. def fact(n): if n == 0: return 1 else: return n * fact(n-1)

Solution

1. Step 1: Check base case correctness

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) uses if n == 0: return 1 which is correct for factorial base case.

2. Step 2: Check recursive call correctness

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) calls fact(n-1) and multiplies by n, which matches factorial definition.

3. Final Answer:

   def fact(n): if n == 0: return 1 else: return n * fact(n-1) -> Option D

4. Quick Check:

   Correct base and recursive case = def fact(n): if n == 0: return 1 else: return n * fact(n-1) [OK]

Hint: Base case returns 1 for factorial; recursive case multiplies by n [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value
• Recursive call increasing n instead of decreasing

3. What will be the output of the following code?

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

countdown(3)

medium

A. 3 2 1 Done

B. 3 2 1

C. Done

D. 3 2 1 0 Done

Solution

1. Step 1: Trace the recursive calls and prints

   Function prints 3, then calls countdown(2), prints 2, calls countdown(1), prints 1, calls countdown(0).

2. Step 2: Base case returns 'Done'

   When n == 0, function returns 'Done' without printing 0.

3. Final Answer:

   3 2 1 -> Option B

4. Quick Check:

   Prints 3,2,1; base case returns 'Done' (not printed) [OK]

Hint: Print happens before recursive call; base case returns 'Done' [OK]

Common Mistakes:

• Expecting 0 to be printed
• Ignoring the need for a stopping condition
• Confusing print order

4. Identify the error in this recursive function that sums numbers from n down to 1:

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

medium

A. Base case condition is wrong

B. Missing return statement in base case

C. Recursive call increases n causing infinite recursion

D. Function should use a loop instead

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum_n(n+1), which increases n, moving away from base case.

2. Step 2: Understand effect on recursion

   Since n increases, base case n == 1 is never reached, causing infinite recursion.

3. Final Answer:

   Recursive call increases n causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n to reach base case [OK]

Hint: Recursive calls must move toward base case by decreasing input [OK]

Common Mistakes:

• Increasing n instead of decreasing
• Wrong base case condition
• Ignoring infinite recursion risk

5. Given the recursive function below, what will be the output when calling mystery(4)? Explain why.

def mystery(n):
    if n <= 0:
        return 0
    else:
        return n + mystery(n-2)

hard

A. 6 (4 + 2 + 0)

B. 10 (4 + 3 + 2 + 1)

C. 4 (only the first call)

D. Error due to missing base case

Solution

1. Step 1: Trace recursive calls with n=4

   mystery(4) calls 4 + mystery(2), mystery(2) calls 2 + mystery(0), mystery(0) returns 0.

2. Step 2: Calculate sum from calls

   Sum is 4 + 2 + 0 = 6.

3. Final Answer:

   6 (4 + 2 + 0) -> Option A

4. Quick Check:

   Recursive case adds n and calls with n-2 until n ≤ 0 [OK]

Hint: Sum n and n-2 recursively until base case n ≤ 0 [OK]

Common Mistakes:

• Assuming all numbers from n down to 1 are added
• Missing base case for n ≤ 0
• Confusing decrement step