Recursion in Python
Recursion is a powerful programming technique where a function calls itself to solve a smaller instance of the same problem. It is often used to solve problems that can be broken down into smaller, similar subproblems. Understanding recursion is crucial for many coding interviews, including those at Google. Here is a comprehensive guide on recursion, its concepts, and examples in Python.
Key Concepts
Base Case
Every recursive function needs a base case that stops the recursion to prevent infinite loops. The base case is the simplest instance of the problem, which can be solved directly without further recursion.
Recursive Case
The recursive case is where the function calls itself with a smaller or simpler argument, moving towards the base case.
Stack Overflow
Recursion uses the call stack to keep track of function calls. If the recursion goes too deep, it can lead to a stack overflow error.
Memoization
Memoization is an optimization technique used to speed up recursive algorithms by storing the results of expensive function calls and reusing them when the same inputs occur again.
Recursion Examples
Factorial
Problem: Calculate the factorial of a number.
Solution:
def factorial(n):
if n == 0: # Base case
return 1
else:
return n * factorial(n - 1) # Recursive case
# Example usage:
print(factorial(5)) # Output: 120
Fibonacci Sequence
Problem: Calculate the nth Fibonacci number.
Solution:
def fibonacci(n):
if n <= 1: # Base cases
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2) # Recursive case
# Example usage:
print(fibonacci(6)) # Output: 8
Fibonacci with Memoization
Problem: Optimize the Fibonacci calculation using memoization.
Solution:
def fibonacci_memo(n, memo={}):
if n in memo: # Check if result is already computed
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
# Example usage:
print(fibonacci_memo(6)) # Output: 8
Binary Search
Problem: Implement binary search using recursion.
Solution:
def binary_search(arr, low, high, target):
if low > high:
return -1 # Base case: target not found
mid = (low + high) // 2
if arr[mid] == target:
return mid # Base case: target found
elif arr[mid] < target:
return binary_search(arr, mid + 1, high, target) # Recursive case: search right half
else:
return binary_search(arr, low, mid - 1, target) # Recursive case: search left half
# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 4
print(binary_search(arr, 0, len(arr) - 1, target)) # Output: 3
Merge Sort
Problem: Implement merge sort using recursion.
Solution:
def merge_sort(arr):
if len(arr) <= 1: # Base case
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid]) # Recursive case: sort left half
right_half = merge_sort(arr[mid:]) # Recursive case: sort right half
return merge(left_half, right_half)
def merge(left, right):
sorted_array = []
while left and right:
if left[0] < right[0]:
sorted_array.append(left.pop(0))
else:
sorted_array.append(right.pop(0))
sorted_array.extend(left or right)
return sorted_array
# Example usage:
arr = [5, 2, 9, 1, 5, 6]
print(merge_sort(arr)) # Output: [1, 2, 5, 5, 6, 9]
Permutations
Problem: Generate all permutations of a list.
Solution:
def permutations(arr):
if len(arr) == 0:
return []
if len(arr) == 1:
return [arr]
perms = []
for i in range(len(arr)):
current = arr[i]
remaining_list = arr[:i] + arr[i+1:]
for p in permutations(remaining_list):
perms.append([current] + p)
return perms
# Example usage:
arr = [1, 2, 3]
print(permutations(arr))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Subset Sum
Problem: Check if there's a subset of the given set with a sum equal to the given sum.
Solution:
def is_subset_sum(arr, n, sum):
if sum == 0:
return True
if n == 0 and sum != 0:
return False
if arr[n-1] > sum:
return is_subset_sum(arr, n-1, sum)
return is_subset_sum(arr, n-1, sum) or is_subset_sum(arr, n-1, sum-arr[n-1])
# Example usage:
arr = [3, 34, 4, 12, 5, 2]
sum = 9
n = len(arr)
print(is_subset_sum(arr, n, sum)) # Output: True
Key Points for Interviews
Understand the base and recursive cases: Clearly identify the base case and recursive case for each problem.
Optimize using memoization: For problems like Fibonacci, use memoization to avoid redundant calculations.
Analyze time complexity: Be able to explain the time complexity of recursive solutions.
Handle large inputs: Be aware of stack overflow issues with deep recursion and understand when to switch to iterative solutions.
Practice: Solve a variety of problems to get comfortable with different types of recursion.
By mastering these concepts and practicing relevant problems, you'll be well-prepared for interview questions on recursion.