Recursion

A recursive function solves a problem by calling itself on a smaller input until it reaches a base case it can answer directly, and the call stack remembers every unfinished call along the way.

Draw the calls as a tree: total time is the work summed over every node, and extra space is the height of the tree, which is the deepest chain of calls.

Split the problem into independent smaller parts, solve each part recursively, then combine the answers, which often turns an O(n^2) approach into O(n log n).

Memoization stores the result of each recursive call by its arguments, so a subproblem that repeats is computed once and then looked up, often turning exponential time into polynomial time.

Any recursion can be rewritten as a loop that manages its own stack (or, for tail recursion and DP, no stack at all), which removes the risk of stack overflow and gives you control over the order of work.