Recursion

Start with the function contract

A recursive function must say what it returns for a smaller instance, identify a base case, and make every call move measurably toward that base case. Prove it by induction: assume the recursive call correctly solves the smaller input, then show the current step combines that result correctly. Count both runtime and call-stack space. For example, linear recursion over n items can be O(n) time and O(n) stack space even when it allocates no extra container. Test empty and singleton inputs, maximum depth, and invalid inputs. Prefer iteration or an explicit stack when depth can exceed runtime limits; tail recursion is not reliably optimized in every language. Avoid recursive calls that repeat identical subproblems unless memoization is added.