Recursion: The Coding Concept That Refers to Itself

RECURSION: THE CODING CONCEPT THAT REFERS TO ITSELF Recursion is a programming technique where a function calls itself to solve a smaller sub-problem. It is useful for tasks that can be broken down into identical, smaller operations. THE TWO CORE RULES OF RECURSION Without a stopping condition, a recursive function would call itself indefinitely, running out of memory and causing a stack overflow error. Every recursive function must implement: 1. THE BASE CASE A terminal condition that returns a value immediately without making another recursive call. 2. THE RECURSIVE CASE The block where the function calls itself, passing a modified input that moves closer to the base case. CALCULATING FACTORIALS RECURSIVELY The factorial of a number (N!) is the product of all positive integers from 1 to N. For example, 4! = 4 * 3 * 2 * 1 = 24. We can express this recursively: - Base Case: If N is 1, return 1. - Recursive Case: N! = N * (N - 1)! Python implementation: def factorial(n): if n == 1: return 1 else: return n * factorial(n - 1) How the CPU evaluates factorial(4): 1. factorial(4) calls 4 * factorial(3) 2. factorial(3) calls 3 * factorial(2) 3. factorial(2) calls 2 * factorial(1) 4. factorial(1) hits base case, returning 1 5. factorial(2) evaluates: 2 * 1 = 2 6. factorial(3) evaluates: 3 * 2 = 6 7. factorial(4) evaluates: 4 * 6 = 24 RECURSION IN PROBLEMS: TOWERS OF HANOI Recursion is helpful for problems like the Towers of Hanoi puzzle. By defining the steps recursively (move N-1 disks to a temporary peg, move the largest disk, then move the N-1 disks to the target peg), a complex puzzle can be solved using simple, readable logic. Reference: Yang Hu, "Algorithms Python.pdf", Chapter 20: Recursive Algorithm & Chapter 27: Towers of Hanoi.