Recursion Concept and Call Stack Visualization in DSA Python - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you want to find the factorial of a number, which means multiplying all whole numbers from that number down to 1. For example, factorial of 4 is 4 x 3 x 2 x 1 = 24.We will learn how to use recursion, a way where a function calls itself to solve smaller parts of the problem, just like breaking a big task into smaller tasks.

🎯 Goal: Build a simple recursive function to calculate factorial of a number and print each step to see how the function calls itself and returns results.

📋 What You'll Learn

Create a function named factorial that takes one parameter n.

Use recursion inside factorial to calculate factorial of n.

Print the current value of n each time the function is called.

Print the result returned by the function for each call.

Call factorial with the value 4 and print the final result.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching files in folders, solving puzzles, and processing tree structures.

💼 Career

Understanding recursion helps in software development, especially in algorithms, data structures, and problem-solving tasks.

1

Create the base case for recursion

Define a function called factorial that takes one parameter n. Inside it, write an if statement to check if n is equal to 1, then return 1.

DSA Python

def factorial(n):
    # Your code here

Hint

The base case stops the recursion. When n is 1, factorial is 1.

2

Add recursive call to factorial function

Inside the factorial function, after the base case, add a return statement that returns n multiplied by factorial(n - 1).

DSA Python

def factorial(n):
    if n == 1:
        return 1
    # Your code here

Hint

The function calls itself with n - 1 to solve smaller parts.

3

Add print statements to visualize recursion calls

Inside the factorial function, add a print statement before the if to show "Calling factorial with n =" and the value of n. Also add a print statement before each return to show "Returning" and the value being returned.

DSA Python

def factorial(n):
    # Your code here

Hint

Print before calling smaller factorial and before returning the result to see the call stack.

4

Call factorial and print the final result

Call the factorial function with the value 4 and store the result in a variable called final_result. Then print "Factorial of 4 is" followed by final_result.

DSA Python

def factorial(n):
    print("Calling factorial with n =", n)
    if n == 1:
        print("Returning", 1)
        return 1
    result = n * factorial(n - 1)
    print("Returning", result)
    return result

# Your code here

Hint

Call the function with 4 and print the final answer to see the full recursion process.

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