Recursion Concept and Call Stack Visualization in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Simple Recursive Sum Function

What is the output of the following Python code that uses recursion to sum numbers from n down to 1?

DSA Python

def recursive_sum(n):
    if n == 0:
        return 0
    else:
        return n + recursive_sum(n-1)

print(recursive_sum(4))

A 24

B 0

C Error: maximum recursion depth exceeded

D 10

💡 Hint

Think about adding numbers from 4 down to 1 step by step.

The function adds 4 + 3 + 2 + 1 + 0 = 10. The base case returns 0 stopping recursion.

❓ Predict Output

intermediate

Output of Recursive Factorial Function

What is the output of this recursive factorial function when called with 3?

DSA Python

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

print(factorial(3))

A 9

B 6

C 3

D Error: maximum recursion depth exceeded

💡 Hint

Factorial of 3 is 3 * 2 * 1.

factorial(3) = 3 * factorial(2) = 3 * 2 * factorial(1) = 3 * 2 * 1 = 6.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci Function

What error will this code produce when calling fibonacci(4)?

DSA Python

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(4))

A RecursionError: maximum recursion depth exceeded

B SyntaxError: unexpected EOF while parsing

C Output: 3

D TypeError: unsupported operand type(s) for +: 'int' and 'str'

💡 Hint

Check the parentheses in the return statement.

The return line was missing a closing parenthesis causing a syntax error. After fixing, the output is 3.

🧠 Conceptual

advanced

Call Stack Depth in Recursive Function

If a recursive function calls itself with n-1 until n is 0, what is the maximum depth of the call stack when called with n=5?

A 6

B 5

C 4

D 1

💡 Hint

Count the initial call plus all recursive calls until base case.

Calls happen for n=5,4,3,2,1,0 so total 6 calls on the stack at deepest point.

🚀 Application

expert

Output of Recursive String Reversal Function

What is the output of this recursive function that reverses a string when called with 'abc'?

DSA Python

def reverse_string(s):
    if s == '':
        return ''
    else:
        return reverse_string(s[1:]) + s[0]

print(reverse_string('abc'))

A 'cba'

B 'abc'

C 'bac'

D Error: maximum recursion depth exceeded

💡 Hint

The function moves first character to the end recursively.

The function calls itself on substring excluding first char and adds first char at end, reversing the string.

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