2 ms·
Recursion can solve problems using larger objects than the input. For instance, a parser for telephone numbers of the form (123)-456-7890 might plausibly conve
by kazinator 6y ago
Recursion can solve problems using larger objects than the input.
For instance, a parser for telephone numbers of the form (123)-456-7890 might plausibly convert the case 1234567890 into this form, which is several characters longer, and then call itself recursively on that form.
So that is to say, a recursive term-rewriting system can be used to solve a problem, and in a term-rewriting system, the path through the rewrites can involve growth as well as shrinkage.
It meets the definition of solving a smaller instance of the sub problem if we take "smaller" as being, simply: "fewer steps remaining".
Recursion can also divide into smaller objects which represent overlapping subdivisions of the input space, but that are together larger than the input and end up creating more work. For instance, naive Fibonacci recursion.
Though, pedantically speaking, the numbers starting from N and the numbers from N+1 are sets of the same size ("countable infinity"), it's still the case that {N+1, ...} is "simpler" than {N, ...}. The latter contains all of the elements of the former, and also N, making it a proper superset, in spite of equivalent cardinality.
Recursion that proceeds from a superset to a proper subset (though they be of the same cardinality) meets the definition of identifying and solving a "smaller instance", though we cannot insist that "smaller" is interpreted in terms of raw set cardinality.
- deleted 6y ago[deleted]