Lesson 6.1: Introduction to Recursion
Recursion is a programming technique where a function calls itself to solve a smaller subproblem of the original. It's particularly useful for solving problems that can be broken down into smaller, similar problems such as tree traversals, factorials, and the Fibonacci sequence.
🔁 Key Points
- Used when a problem can be divided into similar subproblems.
- Needs a base case to stop recursion and avoid infinite loops.
- Useful in mathematical computations like factorial, power, and GCD.
- Enables elegant solutions for tree and graph problems.
- Each recursive call adds to the stack memory.
- Overuse of recursion can lead to stack overflow.
- Tail recursion optimizes performance in some languages.
🧪 Examples
# Recursive Factorial
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
# Fibonacci using Recursion
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
Lesson 6.2: Understanding Backtracking
Backtracking is an algorithmic technique used for finding all or some solutions to a problem by exploring all possible options. If a path fails, it backtracks and tries a different option. It’s widely used in constraint satisfaction problems like Sudoku, N-Queens, and solving mazes.
🎯 Key Points
- Solves problems through trial and error.
- Prunes paths that don't lead to a solution early on.
- Uses recursion to explore decision trees.
- Helps solve puzzles and logic games efficiently.
- Reduces unnecessary computation using constraints.
- Returns to previous state (backtracks) after trying each path.
- Used in AI, constraint satisfaction, and pathfinding algorithms.
🧪 Examples
# Solving N-Queens (conceptual)
def solve(board, row):
if row == len(board):
print(board)
return
for col in range(len(board)):
if is_safe(board, row, col):
board[row][col] = 1
solve(board, row + 1)
board[row][col] = 0
# Maze Solver using Backtracking
def solve_maze(x, y, maze):
if at_end(x, y):
return True
if is_safe(x, y, maze):
mark_path(x, y)
if solve_maze(x+1, y, maze) or solve_maze(x, y+1, maze):
return True
unmark_path(x, y)
return False
Lesson 6.3: Recursion vs Backtracking in Practice
While recursion provides the foundation, backtracking builds on top by systematically exploring paths and pruning those that don't meet constraints. Recursion solves problems like Fibonacci, while backtracking solves constraint-heavy problems like Sudoku. The synergy between them is vital in solving complex, decision-based problems.
⚙️ Key Points
- Recursion simplifies problems via self-calling functions.
- Backtracking explores all valid configurations.
- Backtracking depends on recursive structure.
- Backtracking adds pruning to basic recursion.
- Both use stack memory extensively.
- Backtracking is more powerful for exhaustive search.
- Recursive depth affects time and space complexity.
🧪 Examples
# Recursion: Sum of Digits
def digit_sum(n):
if n == 0:
return 0
return n % 10 + digit_sum(n // 10)
# Backtracking: Word Search in Grid (conceptual)
def word_search(grid, word):
for i in range(len(grid)):
for j in range(len(grid[0])):
if dfs(grid, word, i, j, 0):
return True
return False