3 ms·

Ir is just that you are working with a more general definition of recursion than the actual one: as I said, recursion isn't merely "a function which calls itsel

by saurik 6y ago

Ir is just that you are working with a more general definition of recursion than the actual one: as I said, recursion isn't merely "a function which calls itself", it implies a certain problem solving strategy. Recursion is "a method of solving a problem where the solution depends on solutions to smaller instances of the same problem". If it isn't being broken down into smaller instances towards some base case--an instance small enough to solve on its own--it isn't recursion. The new function you have described is just different, because you have added the bounding into the code, and so now the function itself is solving a different problem: it includes the definition of take inside of it.

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]

by saurik 6y ago

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]