_______ is often used to prove the correctness of a recursive function.

Answer: Mathematical Induction

Why this is used:

Mathematical induction directly matches the structure of many recursive definitions: you prove the property for a base case, then assume it holds for smaller inputs and show it holds for the next case using the recursive step.

1. Base case: Prove the property for the simplest input(s) where the recursion stops.

2. Inductive step: Assume the property holds for smaller inputs (induction hypothesis). Using the recursive definition of the function, prove the property for a general input.

Short example (factorial):

1. Claim: A recursive factorial function returns n! for all n ≥ 0.

2. Base case: n = 0. By definition the function returns 1, which equals 0!.

3. Inductive step: Assume for some k ≥ 0 the function returns k! for input k. For input k+1, the recursive definition computes (k+1) * factorial(k). By the induction hypothesis factorial(k) = k!, so the result is (k+1) * k! = (k+1)!.

Note: For proofs about recursive data structures (like linked lists or trees), structural induction is the analogous technique: prove the property for the base structure and show that if it holds for the components, it holds for the composed structure.