Hacker News Reader

Comment by d-lisp | Hacker News Reader

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.

View on HN

Your 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

Is TCO still rejected by V8 ?

Recursion 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.

Well, if recursion is a species of iteration; then recursion and iteration are not the same thing.

An iterative process can be recursive or not.

I 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

+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

Isn'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.

Reply on news.ycombinator.com