Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to make the recursive function call itself.

DSA Python

def countdown(n):
    if n <= 0:
        print("Blast off!")
    else:
        print(n)
        countdown([1])

Drag options to blanks, or click blank then click option'

An - 1

Bn * 2

Cn

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n leaves the function stuck on the same number.

The function should call itself with n - 1 to count down correctly.

2fill in blank

medium

Complete the code to calculate factorial using recursion.

DSA Python

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

Drag options to blanks, or click blank then click option'

A0

Bn + 1

Cn

Dn - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n does not reduce the problem size.

Factorial multiplies n by factorial of n - 1 until reaching 0.

3fill in blank

hard

Fix the error in the recursive Fibonacci function call.

DSA Python

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci([1]) + fibonacci(n - 2)

Drag options to blanks, or click blank then click option'

An + 1

Bn

Cn - 1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n does not reduce the problem size.

The function should call fibonacci(n - 1) and fibonacci(n - 2) to get the sum.

4fill in blank

hard

Fill both blanks to create a recursive function that sums numbers from n down to 1.

DSA Python

def sum_to_n(n):
    if n == 0:
        return 0
    else:
        return n [1] sum_to_n(n [2] 1)

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of addition.

Not reducing n in the recursive call.

The function adds n to the sum of numbers from n - 1 down to 1.

5fill in blank

hard

Fill all three blanks to create a recursive function that reverses a string.

DSA Python

def reverse_string(s):
    if s == "":
        return ""
    else:
        return s[[1]] + reverse_string(s[[2]:[3]])

Drag options to blanks, or click blank then click option'

A-1

B0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using positive index instead of negative for last character.

Incorrect slicing range causing errors.

The function takes the last character s[-1] and adds the reverse of the string except the last character s[0:-1].

Practice

1. Why do we use recursion instead of loops in some problems?

easy

A. Because recursion can handle problems with self-similar subproblems naturally

B. Because loops are slower than recursion in all cases

C. Because recursion uses less memory than loops always

D. Because loops cannot repeat tasks

Solution

1. Step 1: Understand recursion's nature

   Recursion breaks a problem into smaller similar problems, calling itself to solve each part.

2. Step 2: Compare with loops

   Loops repeat tasks but do not naturally express problems that divide into smaller similar parts.

3. Final Answer:

   Because recursion can handle problems with self-similar subproblems naturally -> Option A

4. Quick Check:

   Recursion = natural for self-similar problems [OK]

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

Common Mistakes:

• Thinking loops are always slower
• Assuming recursion always uses less memory
• Believing loops cannot repeat tasks

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

easy

A. def recurse(n): while n > 0: return n * recurse(n-1)

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

C. def recurse(n): for i in range(n): return recurse(i)

D. def recurse(n): return n * recurse(n+1)

Solution

1. Step 1: Check base case and recursive call

   def recurse(n): if n == 0: return 1 else: return n * recurse(n-1) has a base case (n == 0) and calls itself with smaller n (n-1), correct recursion pattern.

2. Step 2: Verify other options

   Options A and C misuse loops inside recursion; D calls recurse with n+1 causing infinite recursion.

3. Final Answer:

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

4. Quick Check:

   Base case + smaller recursive call = correct recursion [OK]

Hint: Look for base case and smaller recursive call [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops incorrectly inside recursion
• Calling recursion with increasing argument

3. What is the output of this code?

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

print(factorial(4))

medium

A. 24

B. 10

C. Error

D. 120

Solution

1. Step 1: Trace factorial(4) calls

   factorial(4) calls factorial(3), factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0).

2. Step 2: Calculate return values

   factorial(0) returns 1; factorial(1) = 1*1=1; factorial(2) = 2*1=2; factorial(3) = 3*2=6; factorial(4) = 4*6=24.

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial of 4 is 24 [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Expecting 120 which is 5!

4. Find the error in this recursive function that tries to sum numbers from n down to 1:

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

print(sum_down(3))

medium

A. Missing base case for n == 0

B. Return statement should be outside else block

C. Recursive call uses n instead of n-1 causing infinite recursion

D. Function should use a loop instead of recursion

Solution

1. Step 1: Check recursive call argument

   The function calls sum_down(n) again without reducing n, causing infinite recursion.

2. Step 2: Identify fix

   Recursive call should be sum_down(n-1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses n instead of n-1 causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce argument [OK]

Hint: Recursive call argument must decrease to reach base case [OK]

Common Mistakes:

• Not reducing argument in recursive call
• Missing base case for zero
• Thinking loops are required here

5. You want to print all subsets of a set using recursion. Why is recursion better than loops here?

hard

A. Because loops cannot print output

B. Because loops cannot iterate over sets

C. Because recursion uses less memory than loops for subsets

D. Because subsets require exploring all combinations, which is naturally expressed by recursive branching

Solution

1. Step 1: Understand subsets generation

   Generating subsets means choosing to include or exclude each element, creating a branching tree of possibilities.

2. Step 2: Compare recursion and loops

   Recursion naturally handles branching by calling itself twice per element; loops struggle to express this branching clearly.

3. Final Answer:

   Because subsets require exploring all combinations, which is naturally expressed by recursive branching -> Option D

4. Quick Check:

   Recursive branching fits subsets generation [OK]

Hint: Subsets = branching choices, recursion models branching well [OK]

Common Mistakes:

• Thinking loops cannot iterate sets
• Assuming recursion always uses less memory
• Believing loops cannot print