4 ms·
There is a difference between while(true){ } and f=()=>f() In the sense that f will at one point call a function in a function in ... and in som
by d-lisp 3y ago
There is a difference between
while(true){
}
and
f=()=>f()
In the sense that f will at one point call a function in a function in ... and in some languages this will cause an error (maximum call stack). Also I think in some languages: in memory is stored some context that allows us to know how to "get out" of the function f, and within each recursive call of f, memory usage grows (I am no expert).
F is recursive.
While is iterative.
- User23 3y agoRecursion is just a species of iteration for a computing scientist. It's the kind of iteration with an implicit stack (that may be elided for tail calls). There is nothing special about "the stack" other than that pretty much all of our silicon is engineered to make it perform well. So in that sense it's pretty special, but mathematically not so much.
- Mikhail_Edoshin 3y agoIsn't it the other way around? That is isn't iteration a species of recursion? I mean that anything iterative looks to me like a simple (linear) case of recursion. But I can imagine a series of calls that is recursive but not linearly iterative.
- d-lisp 3y agoWell, if recursion is a species of iteration; then recursion and iteration are not the same thing. An iterative process can be recursive or not.
- User23 3y agoI would state that as an iterative procedure can be recursive or not. There are no recursive processes executed by any extant silicon that aren't iteration with a, potentially optional, stack. And once you look at procedures that use two stacks, like this[1], then it becomes pretty apparent just how arbitrary the distinction is. [1] https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF
- betenoire 3y ago+1 This is why I initially asked, to me it is an implementation detail. I was never the best at theoretical computation, especially as it veered more toward math. Chriswarbo's comments helped me see the point of the blog post
- chriswarbo 3y agoYour function `f` is performing a tail-call, and since it's not allocating any new values it should run happily forever in constant space. This is a common way to implement servers, e.g. 'serve = (request) => { respond(request); serve(next_request()); }' Unfortunately some "poorly designed language implementations"[0] will fail to run such functions, with the "stack overflow" you mention. [0] https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO
- d-lisp 3y agoIs TCO still rejected by V8 ?