Hacker News Reader

Comment by betenoire | Hacker News Reader

Admittedly, it's been several decades since I took theory of comp. I left the comment hoping someone would teach me. My understanding is that recursion and non recursion (implementations) are equivalent, but my feeling from the article is that they are not. I vaguely recall having assignments of rewrite the two in the other forms.

- edit I think I see what you are saying, I must not really understand the concept of primitive recursion (or non-, not sure which I don't understand)

View on HN

The article is specifically talking about primitive-recursion versus non-primitive recursion. Primitive recursion is when we only recurse on a "smaller part" of our argument; e.g. the tail of a list, or subtracting 1 from a natural number, or the children of a tree node, etc. We cannot, say, recurse on the next state of a Turing Machine; since that's not a "smaller part" of the previous state.

Primitive recursion is equivalent to a 'for' loop with a pre-computed bound, e.g. 'for i in [0..X]: ...'.

Recursion that's "non-primitive" would include general recursion, which places no restriction on how we recurse; e.g. we could recurse on the next state of a Turing Machine. General recursion is equivalent to a 'while' loop which re-computes its condition after each iteration.

"Non-primitive" recursion can also include other restricted forms of recursion, which do not allow general computation, but cannot be represented by a primitive-recursive form; for example, the (usual definition of the) Ackermann function mentioned in the article takes two arguments, and its recursive calls can increase the second argument (so it's not primitive recursive). However, the pair of arguments always decrease according to (x, y) < (x, y+1) (if the first argument stays the same, the second argument must decrease) and (x, y) < (x+1, z) (if the first argument decreases, we can use anything for the second argument). The latter condition is so permissive that the Ackermann function is allowed to recurse with a second argument that is itself the result of another recursive call. This grows so fast that the number of loop iterations required to implement it cannot be computed by a primitive-recursive function (whatever function we try, there will eventually be an input that requires more iterations than that function returns).

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.

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.

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 ?

Reply on news.ycombinator.com