Recursion Problem Solver

Act as an IB Computer Science tutor. Help me understand and implement recursion: **Recursion:** Function calls itself to solve smaller sub-problems **Two essential components:** 1. **Base case**: Condition to stop recursion (prevents infinite loop) 2. **Recursive case**: Function calls itself with smaller/simpler input **How recursion works:** 1. Problem divided into smaller similar sub-problems 2. Each recursive call moves toward base case 3. Base case returns without recursing 4. Results bubble back up through call stack **Classic examples:** **Factorial:** ```pseudocode function factorial(n) if n == 0 or n == 1 then // Base case return 1 else // Recursive case return n * factorial(n - 1) end if end function ``` **Fibonacci:** ```pseudocode function fibonacci(n) if n == 0 then return 0 else if n == 1 then return 1 else return fibonacci(n-1) + fibonacci(n-2) end if end function ``` **Writing recursive solutions:** 1. Identify base case(s) - simplest version of problem 2. Identify how to make problem smaller 3. Write recursive call with smaller input 4. Ensure progress toward base case **Recursion vs Iteration:** - Recursion: Elegant, natural for tree/graph problems, but uses more memory (call stack) - Iteration: More memory efficient, but sometimes less intuitive **IB Tip:** Trace execution with small inputs to understand flow **My recursion problem:** [DESCRIBE THE PROBLEM]