0/1 Knapsack — Plain Recursion

The problem

Implement `knapsackRecursion(weights, values, capacity)`: given `n` items where item `i` has weight `weights[i]` and value `values[i]`, and a bag that holds `capacity` total weight, return the maximum total value obtainable. Each item is taken whole or not at all — no fractions — which is what the '0/1' names.

`weights = [1, 3, 4, 5], values = [1, 4, 5, 7], capacity = 7` returns `9`: items of weight `3` and `4` fill the bag exactly for `4 + 5`. The greedy pick by value (`7`, weight `5`) leaves only `2` of room and tops out at `8`, which is why greedy isn't a valid strategy here.

The approach

The recursion carries two shrinking parameters and the whole method depends on seeing them as the state: `index` is how many items remain undecided, `capacity` is how much room is left. Every recursive call reduces at least one of them, so the recursion is guaranteed to bottom out.

`index` is seeded with `weights.length` rather than `weights.length - 1`, which makes it a *count* of remaining items rather than a pointer at one. That's why the body reads `weights[index-1]` — the off-by-one lives in exactly one place, and the base case gets to be the clean `index === 0`. Seeding with `length - 1` works too, but then the base case turns into `index < 0` and the shift moves into the recursive calls instead.

The base case is `index === 0 || capacity === 0`, returning `0` for both. Neither is a failure — no items left to consider and no room left to fill both mean 'nothing further can be gained from here', which is a value of zero, not an invalid state.

When the current item fits, both branches are real and the answer is `Math.max` of them: include it (`currentValueOfItem` plus whatever the remaining items can do with `capacity - currentWeightOfItem`) or exclude it (same capacity, one fewer item). Note that including still moves `index` down by one — that's what makes this 0/1 rather than unbounded knapsack, where the include branch would keep the same `index` and allow reuse.

When the item doesn't fit, there's only one legal move, and the separate `return` for it isn't cosmetic. Folding it into the `Math.max` would call the include branch with a negative capacity — it wouldn't crash, but it would let the recursion 'buy' an item it can't afford and quietly overstate the answer. The guard is what makes the include branch safe to write.

The cost is two calls per item in the worst case, so `O(2^n)` time with `O(n)` stack depth. What's structurally interesting is that most of those calls are re-answering questions already answered elsewhere in the tree — take-then-skip and skip-then-take reach the same `(index, capacity)` state — and that redundancy is exactly what the memoized version deletes.

The solution

export function knapsackRecursion(weights, values, capacity) {
    return knapsackRecursionHelper(weights, values, capacity, weights.length)
}

function knapsackRecursionHelper(weights, values, capacity, index) {
    if (index === 0 || capacity === 0) {
        return 0
    }
    const currentWeightOfItem = weights[index-1]
    const currentValueOfItem = values[index-1]
    if (currentWeightOfItem <= capacity) {
        return Math.max(
            currentValueOfItem + knapsackRecursionHelper(weights, values, capacity - currentWeightOfItem, index - 1), // include the item
            knapsackRecursionHelper(weights, values, capacity, index - 1)) // exclude the item
    }
    return knapsackRecursionHelper(weights, values, capacity, index - 1)
}

Time O(2^n)Space O(n)