2 ms·
"To make a list of numbers starting from N, we make a list starting from N+1 and cons N onto the front". How is that not obviously recursive? If we make it a
by kazinator 6y ago
"To make a list of numbers starting from N, we make a list starting from N+1 and cons N onto the front".
How is that not obviously recursive?
If we make it a list from N to M, we can use eager evaluation, over ordinary non-tail recursion on a conventional run-time stack:
1> (defun count-from-to (n m)
(cond
((> n m) nil)
((= n m) (list n))
(t (cons n (count-from-to (succ n) m))))) ;; no lcons
count-from-to
2> (count-from-to 1 10)
(1 2 3 4 5 6 7 8 9 10)
What looks "funny" about the original is the lack of any termination test; how can you return a list of all the numbers from N+1, and then tack N onto the front?
However, that doesn't require any new kind of recursion. The mathematical definition given in English at the top of my comment certainly has no issue; math uses whatever evaluation semantics is needed to make things work out, and frequently describes infinities.
- saurik 6y agoIr 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 agoRecursion 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]