Recursion

By the end, you can

• Explain recursion as a function calling itself on a smaller instance of the same problem.
• Identify and write the base case and recursive case for a simple function like factorial.
• Trace the winding and unwinding of the call stack for a small recursive call.
• Compute intermediate and final return values as the stack unwinds.
• Diagnose both stack-overflow causes: missing base case and non-shrinking input.
• Apply the leap-of-faith mindset to reason about a recursive function without tracing every level.
• State the three rules of recursion and check whether a given function satisfies all three.
• Identify problem domains where recursion is a natural fit.