Introduction to Recursion •- Recursion is a process where a function calls itself. • - Used to solve problems by breaking them into smaller sub-problems. • - Difference from iteration: • • Iteration uses loops. • • Recursion uses function calls with base case.
2.
Structure of RecursiveAlgorithms • - Recursive algorithms have two parts: • • Base Case: Stops recursion. • • Recursive Case: Function calls itself with smaller input. • - Example: Factorial(n) • • Base: factorial(0) = 1 • • Recursive: factorial(n) = n * factorial(n-1)
3.
Advantages and Disadvantagesof Recursion • Advantages: • - Simpler and elegant code. • - Natural for divide-and-conquer problems. • Disadvantages: • - High memory usage (stack frames). • - Risk of stack overflow if base case is missing. • - Sometimes slower than iteration.
4.
Tower of HanoiProblem • - Puzzle with 3 pegs and multiple disks of different sizes. • - Rules: • • Only one disk can be moved at a time. • • A larger disk cannot be placed on a smaller one. • - Recursive nature: Move smaller sub-towers to solve problem.
5.
Recursive Solution toTower of Hanoi • - Algorithm: • • Move n-1 disks from Source to Auxiliary. • • Move last disk from Source to Destination. • • Move n-1 disks from Auxiliary to Destination. • - Example (3 disks): • • Move 2 disks to Aux. • • Move largest disk to Dest.
