Recursion
Task: Move four discs from A to C, never stacking bigger on smaller
Why we need Recursion
Analogy
- Imagine a set of nested Russian dolls.
- To reach the smallest doll, you must open each one in order.
- Recursion works the same way: a problem is solved by breaking it into smaller versions of itself.
What is Recursion?
Definition
- Recursion is when a function calls itself to solve a smaller subproblem.
- It continues until a base case is reached (a condition that stops further calls).
Key components
- Base Case: The simplest scenario that ends recursion.
- Recursive Case: The part where the function calls itself with smaller input.
- Without a base case, recursion leads to infinite loops.
Example: factorial
Python
def factorial(n): if n == 0: # base case return 1 else: # recursive case return n * factorial(n-1)factorial(3) → 3 * factorial(2) → 3 * 2 * factorial(1) → 3 * 2 * 1 * factorial(0) → 6.
Tower of Hanoi
- Classic recursion problem: move disks between rods following rules.
- Each move breaks down into smaller subproblems until only one disk remains.
Advantages
- Elegant and clean code for problems naturally defined recursively.
- Useful for divide-and-conquer algorithms (e.g., quicksort, mergesort).
Limitations
- Can be less efficient due to repeated calls and stack usage.
- May cause stack overflow if base case is missing or input is too large.
🎯 Quick recap
- Recursion = function calling itself.
- Needs a base case to stop.
- Great for problems like factorial, Tower of Hanoi, and sorting algorithms.
Recursion vs Backtracking
| Recursion | Backtracking | |
|---|---|---|
| Definition | A function calling itself to solve smaller subproblems. | A problem-solving technique that explores choices and undoes them if they fail. |
| Key idea | Break problem into smaller versions until a base case is reached. | Try a path, and if it fails, step back and try another. |
| Analogy | Russian dolls: open each until the smallest is reached. | Maze escape: backtrack when hitting a dead end. |
| Use cases | Factorials, Fibonacci, Tower of Hanoi, divide-and-conquer algorithms. | N-Queens, Sudoku solver, maze solving, constraint satisfaction problems. |
| Efficiency | Can be elegant but may repeat work if not optimized (use memoization). | Can be slow for large problems; often improved with pruning. |
| Termination | Stops at a base case. | Stops when all possible paths are explored or a solution is found. |
Key takeaway
- Recursion = breaking problems into smaller versions.
- Backtracking = exploring paths and undoing wrong choices.
- Backtracking often uses recursion internally to explore possibilities.