Recursion

O(n)

A function calls itself on a smaller version of the same problem until a base case stops it, then the results combine on the way back up.

Signals

problem is defined in terms of a smaller version of itselfnested/tree-shaped structure to walk (directory, expression, linked list)compute a count/sum/depth over all sub-elementsnatural base case + recursive case split (factorial, Fibonacci, tree depth)

Template

function recurse(n) {
    if (n <= 0) return 0; // base case
    return n + recurse(n - 1); // recursive case: smaller subproblem
}

Looks similar, isn't

Backtracking: Plain recursion just visits smaller subproblems and returns a value. Backtracking is recursion plus a choose/explore/undo loop that builds and un-builds a path to enumerate every valid arrangement.

n recursive calls doing O(1) work each with no branching -> O(n) time, O(n) call-stack depth. Watch for stack overflow past roughly 1e4-1e5 depth on deep or unbalanced input.

Learn this pattern