Python Recursion Exercises

Which of the following function definitions shows the correct syntax for writing a recursive function in Python?

def func(n):
    if n == 0:
        return 1
    return func(n-1)

def func(n):
    if n == 0:
        return 1
    func(n-1)

def func(n):
    return n func(n-1)

function func(n):
    if n == 0:
        return 1
    else:
        return func(n-1)

This question checks understanding of the syntax rules for recursion in Python:

Option 1: Correct ✅ – Defines a function with def, has a base case, and calls itself properly.
Option 2: Incorrect – Missing return for the recursive call; without it, results are lost.
Option 3: Incorrect – Invalid syntax because n func(n-1) is not a valid expression.
Option 4: Incorrect – Python does not use the keyword function; it uses def.

Key takeaway: A recursive function in Python must be defined with def, include a base case, and call itself with valid syntax using return.

Which of the following functions is recursive?

def square(n):
    return n * n

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

def add(a, b):
    return a + b

def countdown(n):
    if n > 0:
        print(n)
        countdown(n-1)

This question checks the ability to recognize a recursive function:

Option 1: Incorrect – Performs a calculation but does not call itself.
Option 2: Incorrect – Uses a loop to compute factorial, not recursion.
Option 3: Incorrect – A simple addition function, no self-calls.
Option 4: Correct ✅ – The function countdown calls itself with n-1, making it recursive.

Key takeaway: A function is recursive if it explicitly calls itself within its definition.

In a recursive function, what is the purpose of the base case?

To improve the speed of recursion.

To stop the recursion and prevent infinite calls.

To convert recursion into iteration.

To automatically store previous results for optimization.

This question checks the understanding of the base case in recursion:

Option 1: Incorrect – The base case is not about speed; it is about correctness and termination.
Option 2: Correct ✅ – The base case defines the condition where recursion stops, preventing infinite calls and stack overflow errors.
Option 3: Incorrect – Base cases do not change recursion into iteration; they just terminate recursion at the right point.
Option 4: Incorrect – That refers to memoization, not the base case.

Key takeaway: A base case ensures recursion terminates properly. Without it, the recursive function would run indefinitely and cause a stack overflow.

Which of the following statements about recursion is true?

Recursion can only be used for mathematical problems.

Recursion requires both a base case and a recursive step.

Recursion always executes faster than loops.

Recursion does not use the call stack in Python.

This question tests the conceptual understanding of recursion:

Option 1: Incorrect – Recursion is widely used in many areas (tree traversal, sorting, searching), not only math.
Option 2: Correct ✅ – A recursive function needs a base case (to stop) and a recursive step (to continue until base case is reached).
Option 3: Incorrect – Recursion is not always faster; in fact, loops are usually more efficient in Python.
Option 4: Incorrect – Recursion relies heavily on the call stack, where each recursive call is stored until it returns.

Key takeaway: The essential structure of recursion is a base case and a recursive step; missing either leads to incorrect or infinite recursion.

What will be the output of the following recursive function call?

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

print(factorial(4))

10

16

20

24

This problem tests understanding of recursion with the factorial function:

Step 1: factorial(4) = 4 * factorial(3)
Step 2: factorial(3) = 3 * factorial(2)
Step 3: factorial(2) = 2 * factorial(1)
Step 4: factorial(1) = 1 * factorial(0)
Step 5: factorial(0) = 1 (base case)

Now multiplying back:

4 × 3 × 2 × 1 = 24

Correct Answer: Option 4 ✅

Which of the following conditions is essential in every recursive function to prevent infinite recursion?

Using a return statement at the end

Calling the function at least twice within itself

Defining a variable before the function call

Having a base case that stops further recursive calls

Every recursive function must include a base case. The base case is the condition that tells the function when to stop calling itself. Without it, the function would continue calling itself endlessly, leading to a RecursionError in Python.

Option 1: A return statement is important but not enough to stop infinite recursion.
Option 2: Calling the function twice or more is not necessary for recursion.
Option 3: Defining a variable outside does not affect recursion control.
Option 4: Correct. A base case ensures recursion eventually stops.

Correct Answer: Option 4 ✅

In Python, what happens if a recursive function does not have a base case?

The program runs indefinitely without error.

Python automatically detects and stops recursion safely.

It results in a <code>RecursionError</code> after exceeding the recursion depth limit.

The function is executed only once and then terminates.

In Python, if a recursive function lacks a base case, the function will keep calling itself without stopping. This creates an infinite recursion scenario. However, Python has a built-in recursion depth limit (default is 1000 calls).

Option 1: Incorrect, because the program cannot run indefinitely; Python will eventually throw an error.
Option 2: Incorrect, Python does not automatically fix the issue. It just raises an error when the limit is reached.
Option 3: Correct. Python raises a RecursionError: maximum recursion depth exceeded.
Option 4: Incorrect, since the function will not terminate after one call without a base case.

Correct Answer: Option 3 ✅

Which of the following is a valid recursive function definition in Python?

def recurse(x):
    return recurse(x)

def recurse(x):
    if x > 0:
        return recurse(x - 1)

def recurse(x):
    if x == 0:
        return 1
    else:
        return x * recurse(x - 1)

def recurse(x):
    return x + x

A valid recursive function in Python must:

Call itself inside the function body.
Include a base case to stop recursion.

Now let’s analyze the options:

Option 1: Invalid, because it has no base case, leading to infinite recursion.
Option 2: Incomplete, since it lacks a return value when x == 0.
Option 3: Correct. This is a classic factorial implementation using recursion, with a base case (x == 0).
Option 4: Not recursive at all, because the function does not call itself.

Correct Answer: Option 3 ✅

Which of the following functions correctly calculates the sum of all elements in a list using recursion?

def sum_list(lst):
    total = 0
    for i in lst:
        total += i
    return total

def sum_list(lst):
    if len(lst) == 0:
        return 0
    return lst[0] + sum_list(lst[1:])

def sum_list(lst):
    return sum_list(lst)

def sum_list(lst):
    if lst == 0:
        return 0
    return lst[0] + sum_list(lst[1:])

This question tests writing a recursive function to sum elements in a list:

Option 1: Incorrect – Uses iteration, not recursion.
Option 2: Correct ✅ – Base case checks for an empty list, then adds the first element to the sum of the rest of the list recursively.
Option 3: Incorrect – Infinite recursion; no base case and no processing.
Option 4: Incorrect – Base case is invalid; lst == 0 will never be true for a list.

Key takeaway: For list recursion, always define a base case (empty list) and ensure the function reduces the list size on each recursive call.

Which of the following functions correctly returns the nth Fibonacci number using recursion?

def fib(n):
    if n <= 1:
        return n
    return fib(n) + fib(n-1)

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

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

This question tests the correct implementation of the Fibonacci sequence using recursion:

Option 1: Incorrect – Calls fib(n) instead of fib(n-2), causing infinite recursion.
Option 2: Incorrect – Uses iteration, not recursion.
Option 3: Correct ✅ – Proper recursive definition: returns n for base cases (0 or 1) and adds the previous two Fibonacci numbers for others.
Option 4: Incorrect – Incorrect recursive formula; adds 1 instead of the previous Fibonacci number.

Key takeaway: For Fibonacci recursion, always define proper base cases (0 and 1) and reduce n in each recursive call to avoid infinite recursion.

Which of the following functions correctly finds the maximum element in a list using recursion?

def max_in_list(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        max_rest = max_in_list(lst[1:])
        return lst[0] if lst[0] > max_rest else max_rest

def max_in_list(lst):
    return max(lst)

def max_in_list(lst):
    if lst == []:
        return 0
    return max_in_list(lst[1:])

def max_in_list(lst):
    if len(lst) == 0:
        return None
    else:
        return lst[0]

This question tests finding the maximum value in a list using recursion:

Option 1: Correct ✅ – Base case: when list has one element, return it. Recursive step: find the maximum of the rest of the list and compare with the first element.
Option 2: Incorrect – Uses Python’s built-in max function, not recursion.
Option 3: Incorrect – Base case returns 0, does not compare elements, fails for negative numbers.
Option 4: Incorrect – Only returns the first element, ignoring the rest of the list.

Key takeaway: When using recursion for lists, define a base case for a single element, then combine results from recursive calls to solve the problem incrementally.

Which of the following functions correctly reverses a string using recursion?

def reverse_string(s):
    return s[::-1]

def reverse_string(s):
    if len(s) == 0:
        return ""
    return reverse_string(s[1:]) + s[0]

def reverse_string(s):
    for i in range(len(s)-1, -1, -1):
        print(s[i])

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

This question tests using recursion to reverse a string:

Option 1: Incorrect – Uses slicing, not recursion.
Option 2: Correct ✅ – Base case: empty string returns "". Recursive step: reverse the substring excluding the first character and append the first character at the end.
Option 3: Incorrect – Prints characters in reverse but does not return the reversed string.
Option 4: Incorrect – Recursive step adds the first character at the start instead of the end, resulting in the original string.

Key takeaway: Recursive string reversal involves taking the first character, reversing the rest of the string recursively, and appending the first character at the end.

Which of the following functions correctly computes the GCD (Greatest Common Divisor) of two numbers using recursion?

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def gcd(a, b):
    if a == b:
        return 0
    return gcd(a-1, b-1)

def gcd(a, b):
    return a + b

This question tests using recursion to compute the GCD using the Euclidean algorithm:

Option 1: Correct ✅ – Base case: if b == 0, return a. Recursive step: call gcd(b, a % b).
Option 2: Incorrect – Uses iteration instead of recursion.
Option 3: Incorrect – Subtracts 1 from both numbers and may not find the correct GCD; also inefficient.
Option 4: Incorrect – Simply adds numbers; does not compute GCD.

Key takeaway: Recursive GCD relies on the Euclidean algorithm: keep replacing the pair with (b, a % b) until b is 0. The remaining a is the GCD.

Which of the following statements about recursive binary search is true?

Which of the following statements about recursive binary search is true?

Recursive binary search never requires a base case.

Recursive binary search is slower than linear search for all cases.

Recursive binary search requires the list to be sorted and uses a base case to stop recursion.

This question tests understanding of the concepts behind recursive binary search:

Option 1: Incorrect – Binary search only works correctly on sorted lists.
Option 2: Incorrect – Base case is essential to stop recursion when the element is found or the search interval is empty.
Option 3: Incorrect – Binary search is faster than linear search for large sorted lists; its complexity is O(log n).
Option 4: Correct ✅ – Recursive binary search requires a sorted list and a base case to terminate the recursion.

Key takeaway: Recursive binary search relies on dividing the search interval in half, checking the middle element, and using a base case to terminate recursion either when the element is found or when the interval becomes empty.

Which of the following functions correctly checks if a string is a palindrome using recursion?

def is_palindrome(s):
    return s == s[::-1]

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

def is_palindrome(s):
    for i in range(len(s)):
        if s[i] != s[len(s)-1-i]:
            return False
    return True

def is_palindrome(s):
    if s == "":
        return False
    return True

This question tests using recursion to check if a string is a palindrome:

Option 1: Incorrect – Uses slicing, not recursion.
Option 2: Correct ✅ – Base case: string of length 0 or 1 is a palindrome. Recursive step: check if first and last characters are equal and recurse on the substring excluding them.
Option 3: Incorrect – Uses iteration, not recursion.
Option 4: Incorrect – Does not perform any character checks, always returns True or False incorrectly.

Key takeaway: Recursive palindrome checking compares the first and last characters and reduces the problem size by slicing the string until the base case is reached.

Which of the following functions demonstrates multiple recursive calls correctly?

def fib(n):
    return n

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

def fib(n):
    for i in range(n):
        fib(i)

def fib(n):
    return n * fib(n)

This question illustrates multiple recursive calls in a function:

Option 1: Incorrect – Returns n directly, no recursion.
Option 2: Correct ✅ – Each call to fib(n) makes two recursive calls: fib(n-1) and fib(n-2). This is a classic example of recursion with multiple recursive branches.
Option 3: Incorrect – Uses a loop instead of proper recursion to calculate Fibonacci.
Option 4: Incorrect – Recursive call fib(n) calls itself without reducing n, leading to infinite recursion.

Understanding the recursion flow:

When you call fib(4), the function executes as:

fib(4)
├─> fib(3)
│   ├─> fib(2)
│   │   ├─> fib(1) = 1
│   │   └─> fib(0) = 0
│   └─> fib(1) = 1
└─> fib(2)
    ├─> fib(1) = 1
    └─> fib(0) = 0

Finally, all these return values are added together to compute fib(4) = 3.

Key takeaway: Multiple recursive calls occur when a function calls itself more than once in the same call. Understanding the call tree helps visualize how recursion works step by step.

Which of the following functions is an example of tail recursion?

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

def sum_list(lst):
    if not lst:
        return 0
    return lst[0] + sum_list(lst[1:])

def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n-1, acc*n)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

This question explains tail recursion vs normal recursion:

Option 1: Incorrect – Normal recursion; the multiplication happens after the recursive call returns, so it is not tail recursion.
Option 2: Incorrect – Normal recursion with addition after returning from recursion; not tail recursion.
Option 3: Correct ✅ – Tail recursion; the recursive call is the last operation, and all necessary computation is passed through the accumulator acc.
Option 4: Incorrect – Fibonacci recursion involves multiple recursive calls and is not tail recursion.

Understanding Tail Recursion:

In tail recursion, the recursive call is the last operation of the function. This allows some languages to optimize recursion and reuse the same stack frame. Although Python does not optimize tail recursion, understanding the concept is important for algorithm design.

Example flow for factorial_tail(4):

factorial_tail(4, 1) → factorial_tail(3, 4) → factorial_tail(2, 12) → factorial_tail(1, 24) → factorial_tail(0, 24) → returns 24

Key takeaway: Tail recursion passes all necessary computation through parameters and allows the recursive call to be the last operation.

Which of the following functions correctly calculates the sum of all elements in a nested list using recursion?

def sum_nested(lst):
    total = 0
    for i in lst:
        total += i
    return total

def sum_nested(lst):
    return sum(lst)

def sum_nested(lst):
    if lst == []:
        return 0
    return lst[0] + sum_nested(lst[1:])

def sum_nested(lst):
    total = 0
    for i in lst:
        if isinstance(i, list):
            total += sum_nested(i)
        else:
            total += i
    return total

This question tests recursion over nested lists:

Option 1: Incorrect – Works only for flat lists, fails on nested lists.
Option 2: Incorrect – Uses built-in sum, no recursion.
Option 3: Incorrect – Works only for flat lists; does not check for nested lists.
Option 4: Correct ✅ – Checks each element: if it is a list, recursively calculates its sum; otherwise adds the element to total.

Understanding the recursion:

When encountering a nested list like [1, [2, 3], 4]:

sum_nested([1, [2, 3], 4])
→ 1 + sum_nested([2, 3]) + 4
→ 1 + (2 + 3) + 4
→ 10

Key takeaway: Recursive functions can handle arbitrarily nested structures by checking the type of each element and recursing only when needed.

Which of the following statements correctly describes recursive backtracking?

Recursive backtracking always finds the shortest path first.

Recursive backtracking does not require a base case.

Recursive backtracking explores all possibilities, using recursion to go deeper and backtrack when a dead-end is reached.

Recursive backtracking can only be applied to numerical problems.

This question tests understanding of recursion in backtracking algorithms:

Option 1: Incorrect – Recursive backtracking explores possibilities in a depth-first manner; it may not find the shortest path first.
Option 2: Incorrect – A base case is required to stop recursion at dead-ends or when the goal is reached.
Option 3: Correct ✅ – Recursive backtracking explores all possibilities. It goes deeper recursively, and when a path leads to a dead-end, it backtracks to try alternative paths.
Option 4: Incorrect – Backtracking is applicable to puzzles, strings, grids, and combinatorial problems, not just numbers.

Understanding recursive backtracking:

For example, navigating a maze:

1. Start at the entrance.
2. Move to a possible next step recursively.
3. If the path leads to a dead-end, return (backtrack) to the previous step and try another path.
4. Repeat until the exit is found or all paths are exhausted.

Key takeaway: Recursive backtracking is powerful for exploring all options systematically, using recursion to manage the current path and backtracking to previous states when needed.

Why is recursion often used in programming?

Because it avoids the need for base cases.

Because it never uses extra memory.

Because it simplifies solving problems that can be broken into smaller, similar sub-problems.

This question wraps up the key concept of recursion:

Option 1: Incorrect – Recursion is not always faster than iteration; sometimes it is slower due to function call overhead.
Option 2: Incorrect – Every recursive function requires a base case to terminate properly.
Option 3: Incorrect – Recursion can use extra memory due to the call stack, especially for deep recursion.
Option 4: Correct ✅ – Recursion is a natural fit for problems that can be divided into smaller sub-problems, such as factorials, Fibonacci numbers, tree traversal, and combinatorial problems.

Key takeaway: Recursion allows programmers to solve complex problems by defining a function in terms of itself. By focusing on smaller sub-problems and using base cases to terminate, recursion can simplify code readability and logic, especially for hierarchical or divide-and-conquer problems.