15 Recursion Interview Questions and Answers

Recursion is a fundamental concept in computer science and programming, where a function calls itself to solve smaller instances of the same problem. It is a powerful tool for simplifying complex problems and is widely used in algorithms, data structures, and various computational tasks. Understanding recursion is crucial for tackling problems related to tree and graph traversals, dynamic programming, and more.

This article provides a curated set of recursion-related questions and answers to help you prepare for technical interviews. By working through these examples, you will gain a deeper understanding of recursive techniques and be better equipped to demonstrate your problem-solving abilities to potential employers.

Recursion Interview Questions and Answers

1. Explain the importance of a base case in a recursive function.

A base case in a recursive function defines the stopping condition for the recursion. Without it, the function would call itself indefinitely, leading to a stack overflow error. The base case ensures that the recursion will eventually terminate, making the function effective.

Consider this example of a recursive function to calculate the factorial of a number:

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

In this example, the base case is if n == 0, which returns 1. This condition stops the recursion when n reaches 0. Without this base case, the function would continue to call itself with decreasing values of n, eventually leading to a stack overflow.

2. What are the risks associated with using recursion, particularly concerning stack overflow?

Recursion involves a function calling itself to solve a problem. While it can simplify code, it carries risks, particularly stack overflow. This occurs when the call stack exceeds its limit due to too many recursive calls without reaching a base case, leading to an infinite loop.

Example:

def infinite_recursion():
    return infinite_recursion()

# This will cause a stack overflow
infinite_recursion()

To mitigate stack overflow, ensure the recursive function has a well-defined base case. For problems requiring deep recursion, consider iterative solutions or optimizing with techniques like tail recursion or dynamic programming.

3. How would you use memoization to optimize a recursive solution? Provide an example.

Memoization optimizes recursive solutions by storing results of expensive function calls and reusing them for the same inputs, reducing time complexity. This is useful for problems with overlapping subproblems, like the Fibonacci sequence.

Example:

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55

In this example, the fibonacci function uses a dictionary memo to store previous computations. When called with a value of n that has already been computed, it returns the stored result, reducing recursive calls and improving performance.

4. Write a recursive function to perform an in-order traversal of a binary tree.

In-order traversal of a binary tree is a depth-first method where nodes are visited in this order: left subtree, root node, and right subtree. This is useful for binary search trees as it visits nodes in ascending order.

Here’s a recursive function for in-order traversal:

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value, end=' ')
        in_order_traversal(root.right)

# Example usage:
# Constructing a simple binary tree
#       1
#      / \
#     2   3
#    / \
#   4   5

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

in_order_traversal(root)
# Output: 4 2 5 1 3

5. Develop a recursive function to generate all permutations of a given string.

Recursion can be used to generate permutations of a string by swapping characters to create all possible arrangements.

Here’s a recursive function to generate permutations:

def permute(s, answer):
    if len(s) == 0:
        print(answer, end=" ")
        return
    
    for i in range(len(s)):
        ch = s[i]
        left_substr = s[0:i]
        right_substr = s[i+1:]
        rest = left_substr + right_substr
        permute(rest, answer + ch)

string = "ABC"
permute(string, "")

6. Write a recursive function to generate all subsets of a given set.

Recursion can generate all subsets of a set by exploring combinations through inclusion or exclusion of each element.

Here’s a recursive function to generate subsets:

def generate_subsets(nums):
    def backtrack(start, path):
        result.append(path)
        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])

    result = []
    backtrack(0, [])
    return result

# Example usage
nums = [1, 2, 3]
print(generate_subsets(nums))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

7. Implement a recursive solution to the N-Queens problem.

The N-Queens problem can be solved using recursive backtracking. The idea is to place queens one by one in different columns, starting from the leftmost column. When placing a queen in a column, we check for clashes with already placed queens. If no clash is found, we move to the next column and repeat the process. If a clash is found, we backtrack and try the next position.

def is_safe(board, row, col, n):
    for i in range(col):
        if board[row][i] == 1:
            return False
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    for i, j in zip(range(row, n, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
    return True

def solve_n_queens_util(board, col, n):
    if col >= n:
        return True
    for i in range(n):
        if is_safe(board, i, col, n):
            board[i][col] = 1
            if solve_n_queens_util(board, col + 1, n):
                return True
            board[i][col] = 0
    return False

def solve_n_queens(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    if not solve_n_queens_util(board, 0, n):
        return "Solution does not exist"
    return board

n = 4
solution = solve_n_queens(n)
for row in solution:
    print(row)

8. Create a recursive function to solve the Tower of Hanoi problem.

The Tower of Hanoi problem involves moving disks between rods following specific rules. A recursive solution involves moving the top n-1 disks to an auxiliary rod, then moving the nth disk to the target rod, and finally moving the n-1 disks from the auxiliary rod to the target rod.

def tower_of_hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n-1, auxiliary, target, source)

# Example usage:
tower_of_hanoi(3, 'A', 'C', 'B')

9. How would you combine dynamic programming with recursion to solve a problem? Provide an example.

Combining dynamic programming with recursion, known as memoization, involves storing results of expensive function calls and reusing them. This optimizes recursive algorithms by avoiding redundant calculations.

A classic example is the Fibonacci sequence. The naive recursive approach has exponential time complexity due to repeated calculations. Memoization reduces it to linear.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

print(fibonacci(10))  # Output: 55

In this example, the fibonacci function uses a dictionary memo to store previously computed Fibonacci numbers. When called with a value of n that has already been computed, it returns the stored result instead of recalculating it.

10. When should you choose recursion over iteration, and vice versa?

Recursion should be chosen over iteration when the problem can be naturally divided into similar subproblems, such as tree traversals or the Tower of Hanoi. Recursion can make the code more readable for these types of problems. However, recursion can be less efficient due to the overhead of maintaining the call stack and can lead to stack overflow errors for deep recursions.

Iteration should be chosen when performance is a concern, and the problem can be solved using simple loops. Iterative solutions are generally more memory-efficient and can handle larger input sizes without the risk of stack overflow. Iteration is often preferred for problems that involve repetitive tasks, such as traversing arrays or lists.

Example of recursion vs. iteration for calculating the factorial of a number:

Recursion:

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

Iteration:

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

11. Detect and prevent infinite recursion in your code.

To detect and prevent infinite recursion, ensure there is a well-defined base case that terminates the recursion. Use a maximum recursion depth limit to prevent the program from running indefinitely, and implement checks to avoid revisiting the same state or input.

Here is an example:

def factorial(n, depth=0, max_depth=1000):
    if depth > max_depth:
        raise RecursionError("Maximum recursion depth exceeded")
    if n == 0:
        return 1
    return n * factorial(n - 1, depth + 1)

try:
    print(factorial(5))
except RecursionError as e:
    print(e)

In this example, the factorial function includes a depth parameter to track the recursion depth and a maximum depth limit to prevent infinite recursion. The base case is defined as n == 0, which terminates the recursion.

12. Implement a complex recursive algorithm to solve a combinatorial optimization problem, such as the traveling salesman problem.

The traveling salesman problem (TSP) is a classic combinatorial optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the origin city. A recursive approach to solving TSP involves exploring all possible paths and using memoization to store intermediate results to avoid redundant calculations.

The recursive solution can be broken down into the following steps:

• Define a recursive function that takes the current city and a set of visited cities as parameters.
• Base case: If all cities have been visited, return the distance to the starting city.
• Recursive case: For each unvisited city, calculate the total distance by adding the distance from the current city to the unvisited city and the result of the recursive call with the unvisited city as the new current city.
• Use memoization to store and retrieve the results of subproblems to optimize the solution.

Example:

def tsp_recursive(graph, current_city, visited, memo):
    if visited == (1 << len(graph)) - 1:
        return graph[current_city][0]
    
    if (current_city, visited) in memo:
        return memo[(current_city, visited)]
    
    min_cost = float('inf')
    for city in range(len(graph)):
        if visited & (1 << city) == 0:
            cost = graph[current_city][city] + tsp_recursive(graph, city, visited | (1 << city), memo)
            min_cost = min(min_cost, cost)
    
    memo[(current_city, visited)] = min_cost
    return min_cost

def traveling_salesman_problem(graph):
    memo = {}
    return tsp_recursive(graph, 0, 1, memo)

graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print(traveling_salesman_problem(graph))
# Output: 80

13. Explain tail call optimization and its benefits.

Tail call optimization (TCO) improves the performance of recursive functions by reusing the current function’s stack frame for the next function call, rather than creating a new one. This is possible when the recursive call is the last operation in the function, known as a tail call. By reusing the stack frame, TCO can reduce memory usage and prevent stack overflow errors in cases of deep recursion.

Here is a conceptual example to illustrate tail call optimization:

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

In this example, the recursive call to factorial is the last operation in the function, making it a tail call. If Python supported TCO, it would reuse the current stack frame for each recursive call, optimizing memory usage.

14. Describe the divide and conquer strategy and give an example of a recursive algorithm that uses it.

The divide and conquer strategy consists of three main steps:

1. Divide: Break the problem into smaller subproblems of the same type.
2. Conquer: Solve the subproblems recursively. If the subproblems are small enough, solve them directly.
3. Combine: Combine the solutions of the subproblems to form the solution to the original problem.

A classic example of a recursive algorithm that uses the divide and conquer strategy is Merge Sort. Merge Sort works by dividing the array into two halves, recursively sorting each half, and then merging the sorted halves to produce the sorted array.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_array = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])

    return sorted_array

# Example usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)
# Output: [3, 9, 10, 27, 38, 43, 82]

15. Provide examples of real-world applications where recursion is particularly useful.

Recursion is particularly useful in several real-world applications:

• Tree Traversal: Recursion is commonly used to traverse tree data structures, such as binary trees. For example, in-order, pre-order, and post-order tree traversals are naturally implemented using recursion.
• Graph Algorithms: Many graph algorithms, such as Depth-First Search (DFS), are implemented using recursion to explore nodes and edges.
• Divide and Conquer Algorithms: Algorithms like QuickSort and MergeSort use recursion to divide the problem into smaller sub-problems, solve them recursively, and then combine the results.
• Dynamic Programming: Some dynamic programming problems, such as the Fibonacci sequence or the Knapsack problem, can be solved using recursive approaches with memoization to optimize performance.
• Backtracking: Recursion is used in backtracking algorithms to explore all possible solutions, such as solving puzzles like Sudoku or finding all permutations of a set.

Example of a recursive function for calculating the Fibonacci sequence:

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

print(fibonacci(10))  # Output: 55