Recursion, Backtracking and Dynamic Programming

A base case that returns without recursing, and a recursive case that moves strictly toward the base case.

Assume the function already works correctly on smaller inputs and focus only on combining those results for the current input.

Exponentially, about O(phi^n) with phi near 1.618 (often bounded as O(2^n)), because the same subproblems are recomputed in an ever-branching call tree.

Each active call holds a frame with its arguments, locals, and return address; exceeding the stack limit (e.g., Python's default recursion limit of 1000) raises a stack overflow or RecursionError.

A call whose recursive call is the last action; it can be optimized into a loop, but Python and Java do not do this and most JavaScript engines do not either, so assume O(depth) stack.

Divide the problem into smaller subproblems, conquer them recursively, and combine their answers.