Categories
General

Reducing vs decomposing

A small distinction which I remembered about today – it was in the SICP videos I watched a while ago. If a problem A can be reduced to a simpler problem B, then once you’ve made that step you can forget about problem A entirely, safe in the knowledge that the answer to B will do just as well. In contrast, a problem which can be decomposed into sub-problems might yet require the sub-answers to be combined in some way to get the final results. Therefore, you need to do more bookkeeping in order to track the results of the subproblems.

To a programmer, this is just the difference between a tail-call and a non-tail call. But the insight pertains to how some programmer use the phrases “reduces to ..” and “decomposes into ..” to mean two subtly different things.