Recursion vs Iteration When Each Wins in DSA Python - Build Both Approaches

Recursion vs Iteration: When Each Wins

📖 Scenario: Imagine you are helping a friend understand two ways to solve problems: recursion and iteration. You will create simple examples to see when each way works better.

🎯 Goal: Build two small programs: one using recursion and one using iteration to count down numbers. Learn when recursion or iteration is easier or better.

📋 What You'll Learn

Create a recursive function to count down from a number to zero

Create an iterative loop to count down from the same number to zero

Compare outputs of both methods

Print the countdown results

💡 Why This Matters

🌍 Real World

Counting down is a simple example, but recursion is used in tasks like searching trees or solving puzzles, while iteration is common in loops and repeated actions.

💼 Career

Understanding when to use recursion or iteration helps in writing efficient code and solving problems clearly, a key skill for software developers.

1

Create a recursive countdown function

Define a function called countdown_recursive that takes a parameter n. Inside the function, if n is 0, return an empty list. Otherwise, return a list starting with n followed by the result of calling countdown_recursive(n - 1).

DSA Python

# Define countdown_recursive function
# Your code here

Hint

Use a base case when n is 0 to stop recursion. Otherwise, build the list by adding n and calling the function again with n - 1.

2

Create an iterative countdown function

Define a function called countdown_iterative that takes a parameter n. Inside the function, create an empty list called result. Use a for loop with variable i that goes from n down to 1 (inclusive). In each loop, append i to result. After the loop, return result.

DSA Python

def countdown_recursive(n):
    if n == 0:
        return []
    else:
        return [n] + countdown_recursive(n - 1)

# Define countdown_iterative function
# Your code here

Hint

Use a for loop counting down from n to 1. Add each number to the list and return it.

3

Set the starting number for countdown

Create a variable called start_number and set it to 5.

DSA Python

def countdown_recursive(n):
    if n == 0:
        return []
    else:
        return [n] + countdown_recursive(n - 1)

def countdown_iterative(n):
    result = []
    for i in range(n, 0, -1):
        result.append(i)
    return result

# Create start_number variable
# Your code here

Hint

Just create a variable named start_number and assign it the value 5.

4

Print countdown results from both methods

Print the result of calling countdown_recursive(start_number). Then print the result of calling countdown_iterative(start_number).

DSA Python

def countdown_recursive(n):
    if n == 0:
        return []
    else:
        return [n] + countdown_recursive(n - 1)

def countdown_iterative(n):
    result = []
    for i in range(n, 0, -1):
        result.append(i)
    return result

start_number = 5

# Print countdowns
# Your code here

Hint

Use print() to show the lists returned by both functions with start_number as input.

Practice

1. Which scenario is best suited for using recursion instead of iteration?

easy

A. When the problem requires simple repeated loops

B. When you want to avoid function call overhead

C. When memory usage must be minimal

D. When the problem can be divided into similar smaller problems

Solution

1. Step 1: Understand recursion use case

   Recursion works best when a problem can be broken down into smaller similar problems, like tree traversals or factorial calculation.

2. Step 2: Compare with iteration scenarios

   Iteration is better for simple repeated tasks without the need for breaking down problems.

3. Final Answer:

   When the problem can be divided into similar smaller problems -> Option D

4. Quick Check:

   Recursion = divide and conquer [OK]

Hint: Recursion fits problems breaking into smaller similar parts [OK]

Common Mistakes:

• Thinking iteration is always faster
• Ignoring function call overhead in recursion
• Confusing recursion with simple loops

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

easy

A. def func(): return func()

B. def func(n): if n == 0: return 1 else: return n * func(n-1)

C. def func(n): while n > 0: n -= 1 return n

D. def func(n): for i in range(n): return i

Solution

1. Step 1: Identify recursive function structure

   A recursive function calls itself with a smaller input and has a base case to stop recursion.

2. Step 2: Check each option

   def func(n): if n == 0: return 1 else: return n * func(n-1) correctly defines a base case (n == 0) and recursive call (func(n-1)). Others either lack base case or use iteration.

3. Final Answer:

   def func(n): if n == 0: return 1 else: return n * func(n-1) -> Option B

4. Quick Check:

   Base case + self call = recursion [OK]

Hint: Look for base case and self call in function [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursive calls
• Incorrect indentation or syntax errors

3. What is the output of the following Python code?

def factorial_iter(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

print(factorial_iter(4))

medium

A. 24

B. 10

C. 120

D. Error

Solution

1. Step 1: Trace the loop for factorial_iter(4)

   Loop runs i=1 to 4, multiplying result: 1*1=1, 1*2=2, 2*3=6, 6*4=24.

2. Step 2: Return and print result

   Function returns 24, which is printed.

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial of 4 is 24, check loop multiplication [OK]

Common Mistakes:

• Confusing factorial with sum
• Off-by-one errors in loop range
• Expecting recursion output from iteration

4. Identify the error in this recursive function to compute sum of numbers from 1 to n:

def sum_recursive(n):
    if n == 0:
        return 0
    else:
        return n + sum_recursive(n)

medium

A. Recursive call uses same argument causing infinite recursion

B. Function should return n * sum_recursive(n-1)

C. Should use iteration instead

D. Missing base case

Solution

1. Step 1: Check base case and recursive call

   Base case exists for n == 0. Recursive call uses sum_recursive(n) without reducing n.

2. Step 2: Identify infinite recursion cause

   Since n does not decrease, function calls itself endlessly causing stack overflow.

3. Final Answer:

   Recursive call uses same argument causing infinite recursion -> Option A

4. Quick Check:

   Recursive argument must change to avoid infinite calls [OK]

Hint: Recursive call argument must reduce towards base case [OK]

Common Mistakes:

• Forgetting to reduce argument in recursion
• Confusing multiplication with addition in sum
• Ignoring base case importance

5. You need to process a large dataset with a depth of 10,000 recursive calls. Which approach is better and why?

hard

A. Use recursion with no base case for speed

B. Use recursion because it is easier to write

C. Use iteration to avoid stack overflow errors

D. Use iteration but expect high memory usage

Solution

1. Step 1: Understand recursion limits

   Python has a recursion depth limit (usually ~1000). 10,000 calls exceed this causing stack overflow.

2. Step 2: Choose iteration for large depth

   Iteration uses loops and constant stack space, avoiding overflow and handling large datasets safely.

3. Final Answer:

   Use iteration to avoid stack overflow errors -> Option C

4. Quick Check:

   Large depth = iteration to prevent overflow [OK]

Hint: Large recursion depth? Switch to iteration to avoid errors [OK]

Common Mistakes:

• Ignoring recursion depth limits
• Assuming recursion is always simpler
• Not considering memory and stack constraints