Hacker News Reader

Comment by zelphirkalt | Hacker News Reader

I navigated from the post to Zig's documentation, which the author links to. Seems a bit more than one page, but OK. I checked for recursion, as I value being able to use recursion without stack overflow or maximum recursion depth errors. I read:

> Recursion is a fundamental tool in modeling software. However it has an often-overlooked problem: unbounded memory allocation.

That it not necessarily true. It depends on the implementation in the given language. Perhaps in Zig it has that problem, but it is not an inherent property of every recursion one can think of.

If Zig manages to get optimized tail calls like I can enjoy in Scheme, it has a good chance of being the next language I learn. As noted in the next paragraph of the docs, it is still an area of experimentation.

View on HN

Correct me if I'm wrong, but I think it's not possible to express all recursion as tail-call recursion. So I think the statement is correct, in the general case.

But, yes, it's true that you can express some recursion with fixed memory size. And, in fact, the @call[0] built-in has an `always_tail` which asserts that the call should always be generated with tail call recursion optimization, and is an error at compile time, if not.

You might also be interested in following this (open) GitHub issue[1] that explores recursion in more detail.

But, yes, this area of Zig seems to be still a little "experimental", as you say. (But shows great promise, I think!)

[0] https://ziglang.org/documentation/0.7.1/#call [1] https://github.com/ziglang/zig/issues/1006

I think it is possible to express all recursion as tail-call recursion, but only by passing continuations as arguments, which might lose the advantage of a tail-call recursion. Any computation you have left in the current frame you could put into a continuation. However, that continuation then grows, so you need more memory for it, instead of multiple stack frames, so the advantage ist lost.

> That it not necessarily true

It is necessarily true if you allow non-tail recursive calls.

The phrase makes a statement about recursion in general, no further narrowing it down to one kind. One cannot generalize from one case (non-tail recursive, which might have unbounded memory allocation) to the whole class of calls, which is recursive calls or recursion in general.

So it is not necessarily a true statement about recursion. It is only a true statement about non-tail recursive ones. It is an over-generalization. The docs would to well to distinguish those.

~Zig doesn't support TCE.~

Edit: Tried with different optimization levels, it seems it might. I wonder if it's an optimization from LLVM. Nevertheless, I don't think that Zig is the kind of language where you want to use recursion as your primary mean of looping; it's not a functional language, it's a procedural language.

Reply on news.ycombinator.com