What makes a recursive algorithm divide-and-conquer rather than plain recursion?
answer
- Three phases, not just a self-call
- Are the pieces the same problem?
- Do the pieces need each other's answers?
- Something must merge the sub-answers
- A fraction of the input, not one element
basics
~20 sDivide-and-conquer splits a problem into two or more subproblems of the same kind on a fraction of the input, solves them independently, and combines their answers. A function that merely calls itself does none of that by default.
solid answer
~40 sThree things have to hold. First, each subproblem is the *same* problem on strictly smaller input, usually a constant fraction of it — that fraction is what buys logarithmic recursion depth. Second, the subproblems are independent: no branch needs another branch's result, and the recursion does not keep landing on the same subproblem instance. Third, there is a real combine step that builds the whole answer out of the sub-answers. Recursion that peels off one element per call is decrease-and-conquer — same skeleton, a very different recurrence. Recursion whose branches keep revisiting the same subproblem is dynamic-programming territory. And in practice the combine step, not the split, is where the design work lives: splitting is usually obvious, merging correctly and cheaply usually is not.
go deeper
Be ready to name the three phases and, more importantly, to say what the subproblems must look like: same problem, smaller input, no dependence on each other. Mentioning the base case unprompted reads well.
Explain how the branching factor, the shrink factor and the per-call work outside the recursion together determine the total cost, and why a split into one element plus the rest gives linear depth rather than logarithmic.
Show you can apply the test to an unfamiliar problem: can it be cut into pieces that do not need each other, and could you cheaply assemble the whole answer from theirs? Say out loud where the combine step would be hard.
Own the framing that the paradigm is a design tool, not a performance promise. Be prepared to argue when a decomposition is worth its constants and its maintenance burden versus a straightforward pass over the data.
## The skeleton Divide and conquer is a recursive shape with three named phases: 1. **Divide** — cut the input into smaller instances of the *same* problem. Typically two pieces of roughly `n/2`, but nothing requires exactly two, and nothing requires them to be equal. 2. **Conquer** — solve each piece by recursing, until the piece is small enough to answer directly. That stopping point is the **base case**; without it the recursion never terminates. 3. **Combine** — assemble the whole answer from the sub-answers. Written as a cost model, that becomes a recurrence: if you make `a` recursive calls on inputs of size `n/b`, and do `f(n)` work outside the calls (splitting plus combining), then `T(n) = a * T(n/b) + f(n)`. Formally solving such recurrences is its own topic; what matters at the paradigm level is that the three phases map onto the three knobs `a`, `b` and `f(n)`. ## What actually distinguishes it from ordinary recursion Not every self-calling function is divide and conquer. Three properties do the distinguishing: **Same problem, smaller input.** The recursive call must answer the identical question on a smaller instance. A recursive routine that walks a structure while accumulating unrelated side effects is recursion, not decomposition. **A constant-fraction shrink.** Cutting the input by a constant factor gives about `log n` levels of recursion. Cutting off one element gives `n` levels. Both are legal recursions; only the first gets the depth benefit people associate with the paradigm. A split into one element plus the remaining `n-1` has linear depth even though it "divides". **Independence.** No subproblem may require another subproblem's result, and the recursion should not keep arriving at the same subproblem instance through different paths. Independence is what lets you reason about the branches separately at all — and it is exactly the property that fails when the right answer is dynamic programming, where the same subinstance is reachable through many different splits and must be remembered rather than recomputed. **A combine step that exists.** If there is nothing to merge, you probably have a *reduction*: one branch, no assembly. Halving a search range and continuing in one half is that shape — the recursion narrows rather than splitting. ## Decrease-and-conquer, the near neighbour When the recursion produces exactly one subproblem, the usual name is decrease-and-conquer. It comes in two flavours: decrease by a constant (peel one element, recurse on `n-1`) and decrease by a factor (halve the input, recurse on one half). Both keep the recursive skeleton and drop the branching, and the recurrence shape changes completely as a result: `T(n) = T(n/2) + O(1)` is logarithmic, while `T(n) = T(n-1) + O(n)` is quadratic. Recognising which of the two shapes you are holding is more useful in an interview than reciting the phase names. ## Borderline cases worth being honest about Aggregating over a tree — computing its height, or the sum of its values, from the answers for its two subtrees — genuinely *is* divide and conquer: the subtrees are independent instances of the same problem and the addition is the combine. What it lacks is a size guarantee; an unbalanced tree gives no logarithmic depth, only depth equal to the tree's height. That is a useful reminder that the paradigm promises structure, not a running time. Conversely, a traversal that visits nodes to print them has no combine step and returns nothing to merge; calling it divide and conquer adds no insight. ## Why interviewers ask this The question separates people who memorised three phase names from people who can look at an unfamiliar problem and ask the two design questions that matter: *can I cut this into pieces that don't need each other?* and *if I had the answers for the pieces, could I cheaply build the whole answer?* If the answer to the first is no, you are heading toward dynamic programming. If the answer to the second is no, the paradigm buys nothing, because the combine step's cost will dominate everything the recursion saved.
- Is a recursion that sums a binary tree's node values divide-and-conquer?Yes, honestly so: the two subtrees are independent instances of the same problem and the addition is the combine step. What it lacks is a size guarantee — the recursion depth is the tree's height, which on a skewed tree is linear, so you get the paradigm's structure without its logarithmic depth.
- If the second subproblem cannot start until the first one's answer is known, what does that tell you?That the subproblems are not independent, so it is not divide and conquer. You have a sequential reduction — each step consumes the previous result — which is analysed as a chain, not as a branching recurrence, and which usually turns into an iterative loop or a dynamic-programming pass.
- Does divide-and-conquer require splitting into exactly two pieces?No. Two is the common case, but nothing in the paradigm requires it: splitting into three or more subproblems, or into unequal pieces, is still divide and conquer. The branching factor is simply another knob that changes the recurrence and therefore the total cost.
Counting a stadium crowd by giving two people one half each and adding their totals. It only helps because no seat is counted twice and because adding two numbers is cheap.
saying these in an interview costs you the question
- Says any function that calls itself is divide-and-conquer
- Treats the combine step as trivial glue
- Insists divide-and-conquer must split into exactly two equal halves
- Cannot distinguish independent subproblems from overlapping ones
- Assumes any split gives logarithmic recursion depth