From Newsgroup: comp.lang.c

On 2026-09-25 12:01, Alan Mackenzie wrote:

In comp.theory Dude <punditster@gmail.com> wrote:

By banning unbounded loops and wild recursion, you ensure that every
valid program in the language is guaranteed to finish

No. Besides, unbounded loops (such as event loops) are necessary.
Recursion is, too, if you want to program things like tree structures.

Note that recursion isn't "necessary" to program [operations on]
tree structures. It just makes the algorithms appear simpler and
clearer, thus recursion is a sensible technique to implement
application cases like those. WRT Dude's statement it should be
mentioned that a recursive algorithm can be transformed to an
iterative one, so if iterative algorithms would have the property
to be _decidable_ to finish - actually, they are not - we could
also say the same for a recursive one.

Janis

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 12:01, Alan Mackenzie wrote:

In comp.theory Dude <punditster@gmail.com> wrote:

By banning unbounded loops and wild recursion, you ensure that every
valid program in the language is guaranteed to finish

No. Besides, unbounded loops (such as event loops) are necessary. Recursion is, too, if you want to program things like tree structures.

Note that recursion isn't "necessary" to program [operations on]
tree structures. It just makes the algorithms appear simpler and
clearer, thus recursion is a sensible technique to implement
application cases like those.

Some things you need to do on trees need either explicit recursion, or "simulated recursion", where static arrays are used to hold intermediate
values of variables. This approach limits the depth of a tree, possibly
more so than the size of the stack when using explicit recursion. We
might just be arguing about the meaning of words here.

WRT Dude's statement it should be mentioned that a recursive algorithm
can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they
are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice. In theory,
there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without recursion.

Janis

--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 12:01, Alan Mackenzie wrote:

In comp.theory Dude <punditster@gmail.com> wrote:

By banning unbounded loops and wild recursion, you ensure that every
valid program in the language is guaranteed to finish

No. Besides, unbounded loops (such as event loops) are necessary.
Recursion is, too, if you want to program things like tree structures.

Note that recursion isn't "necessary" to program [operations on]
tree structures. It just makes the algorithms appear simpler and
clearer, thus recursion is a sensible technique to implement
application cases like those.

Some things you need to do on trees need either explicit recursion, or "simulated recursion", where static arrays are used to hold intermediate values of variables. This approach limits the depth of a tree, possibly
more so than the size of the stack when using explicit recursion. We
might just be arguing about the meaning of words here.

The difference is an explicitly programmed stack vs. an implicitly
used stack. Any practical size limitations apply to both, recursion
and iterative replacements.

(I don't know whether we are arguing about meaning of words; I was
just pointing out the non-"necessity", i.e. on the word you used.)

WRT Dude's statement it should be mentioned that a recursive algorithm
can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they
are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice. In theory,
there are recursively defined functions which grow too quickly with increasing argument to be definable (or programmable) without recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Janis

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 25/09/2026 12:01, Alan Mackenzie wrote:

[ Followup-To: set ]

In comp.theory Dude <punditster@gmail.com> wrote:

[ .... ]

You can use restricted programming languages or subsets (such as MISRA
C, SPARK, or Rocq) that are not fully Turing-complete.

MISRA C is turing-complete, just as C is. I don't know about the
others, but it is likely they are turing-complete too.

MISRA C is a subset of C which supposedly reduces error possibilities,
at the expense of bloat. As far as I'm aware, no studies have been done which show that MISRA C is in fact better than full C, for any value of "better". It is a religion in programming for automotive applications,
no more to be questioned than the Lord's Prayer in a Christian church.

By banning unbounded loops and wild recursion, you ensure that every
valid program in the language is guaranteed to finish

MISRA C does not ban unbounded loops or recursion. That's a good thing,
since it is used primarily in embedded systems (with the automotive
industry as the main target) - programs on microcontrollers do not
normally "finish" until you turn off the power.

No. Besides, unbounded loops (such as event loops) are necessary.
Recursion is, too, if you want to program things like tree structures.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

WRT Dude's statement it should be mentioned that a recursive algorithm
can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they
are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice. In theory, there are recursively defined functions which grow too quickly with increasing argument to be definable (or programmable) without recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

If memory serves me correctly (which it probably doesn't),
A(0, 0) = 0.
A(1, 1) = 1.
A(2, 2) = 5.
A(3, 3) = 63.
A(4, 4) = 2^2^2^2^2^2^2 + 3
A(5, 5) is much bigger still.

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

But I'll accept that for typical practical programming, a recursive
algorithm can be recast iteratively, with explicitly maintained stacks.
A few years back the Emacs Lisp reader was optimised for speed this way.

Janis

--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 25/09/2026 16:10, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

WRT Dude's statement it should be mentioned that a recursive algorithm >>>> can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they
are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice. In theory,
there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

If memory serves me correctly (which it probably doesn't),
A(0, 0) = 0.
A(1, 1) = 1.
A(2, 2) = 5.
A(3, 3) = 63.

I think those last two should be 7 and 61.

A(4, 4) = 2^2^2^2^2^2^2 + 3

If correct, that value would be:

(2 ** 2 ** 2003...6736) + 3

That third number has over 19000 digits. I think it is equivalent to this:

(2 ** X)

where X has about 2**2003...6736/3 digits.

The size of the stack might then be the smaller issue! But then, the
stack needs to be tens of thousands deep just to do A(3, 10) where the
numbers involved are small.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Alan Mackenzie <acm@muc.de> writes:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[...]

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

If memory serves me correctly (which it probably doesn't),
A(0, 0) = 0.
A(1, 1) = 1.
A(2, 2) = 5.
A(3, 3) = 63.
A(4, 4) = 2^2^2^2^2^2^2 + 3
A(5, 5) is much bigger still.

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Who says the arrays have to be static? You could allocate an
array using malloc() and expand it as needed using realloc().
Or you could use a linked list.

[...]
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

Alan Mackenzie <acm@muc.de> writes:

[ .... ]

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

[ .... ]

This function can't be calculated iteratively, since there's no non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Who says the arrays have to be static? You could allocate an
array using malloc() and expand it as needed using realloc().
Or you could use a linked list.

You mean, implement a stack of unbounded size? If you do that, you are implementing a recursive algorithm, surely? The point under discussion
is whether or not Ackermann's function can be implemented without using recursion.

[...]

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Alan Mackenzie <acm@muc.de> writes:

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

Alan Mackenzie <acm@muc.de> writes:

[ .... ]

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

[ .... ]

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Who says the arrays have to be static? You could allocate an
array using malloc() and expand it as needed using realloc().
Or you could use a linked list.

You mean, implement a stack of unbounded size? If you do that, you are implementing a recursive algorithm, surely? The point under discussion
is whether or not Ackermann's function can be implemented without using recursion.

Yes, I mean implementing a stack of unbounded size.

It depends on what you mean by "recursive algorithm". Using an
explicit stack that can grow as needed is a way to implement
something like Ackermann's function without functions that call
themselves, directly or indirectly.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 25/09/2026 23:05, Keith Thompson wrote:

Alan Mackenzie <acm@muc.de> writes:

Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:

Alan Mackenzie <acm@muc.de> writes:

[ .... ]

Yes, it was the Ackermann function I had in mind (though I'd forgotten >>>> its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

[ .... ]

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Who says the arrays have to be static? You could allocate an
array using malloc() and expand it as needed using realloc().
Or you could use a linked list.

You mean, implement a stack of unbounded size? If you do that, you are
implementing a recursive algorithm, surely? The point under discussion
is whether or not Ackermann's function can be implemented without using
recursion.

Yes, I mean implementing a stack of unbounded size.

It depends on what you mean by "recursive algorithm". Using an
explicit stack that can grow as needed is a way to implement
something like Ackermann's function without functions that call
themselves, directly or indirectly.

In computation theory (and the Ackermann function is only of theoretical interest - it has no practical use!), there is no difference between
loops and functions that call themselves - it is all recursion. And it doesn't matter if your "stack" is a call stack, a static array, a
heap-based linked list, or whatever.

The thing that is special about the Ackermann function is that it is not "primitive recursive". That does not mean you can't implement it with a
loop and an array to hold your stack. Basically, it means that you
don't know an upper bound on your stack size in advance.

If you take something like the quicksort algorithm for comparison. That
is most clearly implemented in most languages with recursive functions,
but you can certainly handle it with loops and heap-allocated (or even
alloca allocated) stacks. You can also use a single allocation for
this, because you can find an upper bound - if your input data is length
"n", a stack of size n^2 will definitely be big enough.

You can implement the Ackermann function without explicit recursion,
just using a single loop and with allocated stacks or lists to hold the progress. But you /cannot/ do so with a single allocation at the start.
If you are asked to calculate A(m, n), you cannot calculate an upper
bound on the stack size you need without calculating the function.

But with malloc() and realloc(), you are good to go!



--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

David Brown <david.brown@hesbynett.no> wrote:

[ .... ]

In computation theory (and the Ackermann function is only of theoretical interest - it has no practical use!), there is no difference between
loops and functions that call themselves - it is all recursion. And it doesn't matter if your "stack" is a call stack, a static array, a
heap-based linked list, or whatever.

The thing that is special about the Ackermann function is that it is not "primitive recursive". That does not mean you can't implement it with a loop and an array to hold your stack. Basically, it means that you
don't know an upper bound on your stack size in advance.

If you take something like the quicksort algorithm for comparison. That
is most clearly implemented in most languages with recursive functions,
but you can certainly handle it with loops and heap-allocated (or even alloca allocated) stacks. You can also use a single allocation for
this, because you can find an upper bound - if your input data is length "n", a stack of size n^2 will definitely be big enough.

You can implement the Ackermann function without explicit recursion,
just using a single loop and with allocated stacks or lists to hold the progress. But you /cannot/ do so with a single allocation at the start.
If you are asked to calculate A(m, n), you cannot calculate an upper
bound on the stack size you need without calculating the function.

Thanks, David, for the clarification.

But with malloc() and realloc(), you are good to go!

--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 9/25/2026 9:48 PM, Alan Mackenzie wrote:

Note that recursion isn't "necessary" to program [operations on]
tree structures. It just makes the algorithms appear simpler and
clearer, thus recursion is a sensible technique to implement
application cases like those.

Some things you need to do on trees need either explicit recursion, or "simulated recursion", where static arrays are used to hold intermediate values of variables. This approach limits the depth of a tree, possibly
more so than the size of the stack when using explicit recursion. We
might just be arguing about the meaning of words here.

For some algorithms, but not all, you can code with tail recursion, and therefore have /unbounded/ size of the tree. For some value of unbound-
ded.

Many algorithms can be made tail recursive [1] by adding a parameter or
two to the function call.


Best wishes, and happy tail recursion.

[1] Irrespective of if the compiler has /tail recursive optimizations/.
--
Johann | email: invalid -> com | http://www.myrkraverk.com/blog/
I'm not from the Internet, I just work there. | via Easynews.com https://bsky.app/profile/myrkraverk.bsky.social | for ( ;; ) _:;
Federated at https://fed.brid.gy/bsky/myrkraverk.bsky.social
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 9/25/2026 3:01 AM, Alan Mackenzie wrote:

[ Followup-To: set ]

In comp.theory Dude <punditster@gmail.com> wrote:

[ .... ]

You can use restricted programming languages or subsets (such as MISRA
C, SPARK, or Rocq) that are not fully Turing-complete.

MISRA C is turing-complete, just as C is. I don't know about the
others, but it is likely they are turing-complete too.

MISRA C is a subset of C which supposedly reduces error possibilities,
at the expense of bloat. As far as I'm aware, no studies have been done which show that MISRA C is in fact better than full C, for any value of "better". It is a religion in programming for automotive applications,
no more to be questioned than the Lord's Prayer in a Christian church.

By banning unbounded loops and wild recursion, you ensure that every
valid program in the language is guaranteed to finish

No. Besides, unbounded loops (such as event loops) are necessary.
Recursion is, too, if you want to program things like tree structures.

We can use C to code for the MISRA std. Heck even C++:

https://www.stroustrup.com/JSF-AV-rules.pdf
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Alan Mackenzie <acm@muc.de> writes:

Yes, it was the Ackermann function I had in mind (though I'd
forgotten its name). It's a function of two natural number
arguments. Simply making both arguments the same gives a
function of one argument.

If memory serves me correctly (which it probably doesn't),
A(0, 0) = 0.
A(1, 1) = 1.
A(2, 2) = 5.
A(3, 3) = 63.
A(4, 4) = 2^2^2^2^2^2^2 + 3
A(5, 5) is much bigger still.

This function can't be calculated iteratively, [...]

Of course the Ackermann function can be calculated iteratively,
as it can be computed by a Turing Machine, and Turing Machines
don't have recursion.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 2026-09-25 17:10, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

WRT Dude's statement it should be mentioned that a recursive algorithm >>>> can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they
are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice. In theory,
there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

[...]

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Franky, I'm too lazy now to derive the iterative form myself. But
if you're not convinced by the principle considerations it's fairly
easy to ask an AI to create some C-code, verify that it has no
recursive calls, and check its results. - The code that the AI had
provided to me seems to work well.[*]

Janis

[*] http://volatile.gridbug.de/ack_iterative.c
(only slightly adjusted version to accept command line arguments)

[...]

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 28/09/2026 12:08, Janis Papanagnou wrote:

On 2026-09-25 17:10, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

WRT Dude's statement it should be mentioned that a recursive algorithm >>>>> can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they >>>>> are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice.-a In theory, >>>> there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without
recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name).-a It's a function of two natural number arguments.-a Simply
making both arguments the same gives a function of one argument.

[...]

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be.-a Or something like that.

Franky, I'm too lazy now to derive the iterative form myself. But
if you're not convinced by the principle considerations it's fairly
easy to ask an AI to create some C-code, verify that it has no
recursive calls, and check its results. - The code that the AI had
provided to me seems to work well.[*]

Actually any recursive code in C can be implemented without recursion.
You don't have to change the source code. Example:

c:\cx>cc -r ack
Compiling ack.c to ack.(run)
A= 8189

c:\cx>cc -i ack
Compiling ack.c to ack.(int)
A= 8189

The first invocation runs native code that uses actual recursive calls
with a hardware stack.

The second invocation interprets it. It uses a software stack, and an iterative loop to execute the bytecode instructions.

The difference from your machine-generated Ackermann is that that was
specific to the task, but my approach can run C programs in general
without a stack.

(It also uses a hardware stack for some features of the interpreter, but
your version uses one too for the function calls.)
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 28/09/2026 13:08, Janis Papanagnou wrote:

On 2026-09-25 17:10, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 15:48, Alan Mackenzie wrote:

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

[ .... ]

WRT Dude's statement it should be mentioned that a recursive algorithm >>>>> can be transformed to an iterative one, so if iterative algorithms
would have the property to be _decidable_ to finish - actually, they >>>>> are not - we could also say the same for a recursive one.

Recursion can often be programmed iteratively in practice.-a In theory, >>>> there are recursively defined functions which grow too quickly with
increasing argument to be definable (or programmable) without
recursion.

Have you functions like fib() in mind? - Despite they are cascaded
recursion you can create iterative ones. - But it's simpler; just
recognize that a recursion is using an implicit stack, so you can
write it in iterative form with an explicit stack. Even an extreme
function like Ackermann (which is more demanding) is not exempt to
that principle. - Or do you disagree? (Then please explain - best
with an example you may have in mind.)

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name).-a It's a function of two natural number arguments.-a Simply
making both arguments the same gives a function of one argument.

[...]

This function can't be calculated iteratively, since there's no
non-recursive way of calculating how big the requisite static arrays
would have to be.-a Or something like that.

Franky, I'm too lazy now to derive the iterative form myself. But
if you're not convinced by the principle considerations it's fairly
easy to ask an AI to create some C-code, verify that it has no
recursive calls, and check its results. - The code that the AI had
provided to me seems to work well.[*]

The point is (and it's already be covered in this thread) that there is
no way in advance to know how big a stack you will need to calculate
A(m, n) even when you know m and n. It is not sufficient to just pick a
big number and halt with an error message if you exceed it. The actual iterative or recursive form of the algorithm doesn't matter.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:

On 2026-09-25 17:10, Alan Mackenzie wrote:

[ .... ]

Yes, it was the Ackermann function I had in mind (though I'd forgotten
its name). It's a function of two natural number arguments. Simply
making both arguments the same gives a function of one argument.

[...]

This function can't be calculated iteratively, since there's no non-recursive way of calculating how big the requisite static arrays
would have to be. Or something like that.

Franky, I'm too lazy now to derive the iterative form myself.

I understand the laziness. ;-)

But if you're not convinced by the principle considerations it's fairly
easy to ask an AI to create some C-code, verify that it has no
recursive calls, and check its results. - The code that the AI had
provided to me seems to work well.[*]

David Brown clarified on Saturday what I really should have said, had I
been on the ball with computing theory. The Ackermann function is not _primitive recursive_. It can't be calculated in any bounded amount of
storage which can be determined at the start of the calculation.

Your iterative solution will be continually increasing the amount of
store it uses as it goes along. A normal way of doing this implicitly
is with recursion.

I don't think we're really in disagreement about anything substantial
here.

Janis

[*] http://volatile.gridbug.de/ack_iterative.c
(only slightly adjusted version to accept command line arguments)

--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 2026-09-28 14:08, David Brown wrote:

The point is (and it's already be covered in this thread) that there is
no way in advance to know how big a stack you will need to calculate
A(m, n) even when you know m and n.-a It is not sufficient to just pick a big number and halt with an error message if you exceed it.-a The actual iterative or recursive form of the algorithm doesn't matter.

I think that point has already been covered by another poster in this
thread.

Janis

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 2026-09-28 14:17, Alan Mackenzie wrote:

David Brown clarified on Saturday what I really should have said, had I
been on the ball with computing theory. The Ackermann function is not _primitive recursive_. It can't be calculated in any bounded amount of storage which can be determined at the start of the calculation.

Yes, memory is limited. But you can extend the storage on the fly.
Both versions, recursive or iterative, will bite the dust when the
memory will be exhausted.

The point is that some _very specific_ sorts of recursions don't
need any stack space at all, they can even be linearized with O(1)
space demand. (Not so ack() or similar cascaded recursions.)

(I acknowledge that you may have wanted to say something different.)

Your iterative solution will be continually increasing the amount of
store it uses as it goes along. A normal way of doing this implicitly
is with recursion.

Not "my solution", please. - The algorithm also did not "increase"
(in the sense of realloc()) the amount of store it uses; it just
writes to a pre-allocated linear memory in a stack-operation-mode.
(A recursive algorithm would also have such a stack implicitly.)

I don't think we're really in disagreement about anything substantial
here.

I also hope and suppose so. :-)

Janis

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 9/25/2026 8:10 AM, Alan Mackenzie wrote:
[...]

Recursion in AppleSoft BASIC:

https://pastebin.com/raw/Effeg8cK

100 REM ct_vfield_applesoft_basic
110 HOME
120 HGR: HCOLOR = 3: VTAB 22
130 PRINT "ct_vfield_applesoft_basic"
140 GOSUB 1000
150 GOSUB 3000
160 SP = 0
170 RS(SP, 0) = 0
180 RS(SP, 1) = -1
190 RS(SP, 2) = 0
200 RS(SP, 3) = 1
210 RS(SP, 4) = 0
220 GOSUB 8000
230 V1(1) = 0: V1(2) = 0: V1(3) = 1: V1(4) = 128
240 GOSUB 6000
245 PRINT "Chris Thomasson's Koch Complete!"
250 END

1000 REM ct_init
1010 PRINT "ct_init"
1020 DIM A0(6)
1030 DIM V0(4)
1040 DIM V1(4)
1050 DIM V2(4)
1060 DIM V3(4)
1070 DIM V4(4)
1080 DIM V5(4)
1090 RN = 3
1100 DIM RS(RN, 16)
1110 GOSUB 2000
1120 RETURN

2000 REM ct_init_plane
2010 PRINT "ct_init_plane"
2020 A0(1) = 279: REM m_plane.m_width
2030 A0(2) = 191: REM m_plane.m_height
2040 A0(3) = 0.0126106: REM m_plane.m_xstep
2050 A0(4) = 0.0126316: REM m_plane.m_ystep
2060 A0(5) = -1.75288: REM m_plane.m_axes.m_xmin
2070 A0(6) = 1.2: REM m_plane.m_axes.m_ymax
2080 RETURN

3000 REM ct_display_plane
3010 PRINT "ct_display_plane"
3020 FOR I0 = 1 TO 6
3030 PRINT "A0("; I0; ") = " A0(I0)
3040 NEXT I0
3050 RETURN

4000 REM ct_project_point
4010 REM PRINT "ct_project_point"
4020 V0(3) = (V0(1) - A0(5)) / A0(3)
4030 V0(4) = (A0(6) - V0(2)) / A0(4)
4040 IF V0(3) < 0 THEN V0(3) = INT(V0(3) - .5)
4050 IF V0(3) >= 0 THEN V0(3) = INT(V0(3) + .5)
4060 IF V0(4) < 0 THEN V0(4) = INT(V0(4) - .5)
4070 IF V0(4) >= 0 THEN V0(4) = INT(V0(4) + .5)
4080 RETURN

5000 REM ct_plot_point
5010 REM PRINT "ct_plot_point"
5020 GOSUB 4000
5030 IF V0(3) > -1 AND V0(3) <= A0(1) AND V0(4) > -1 AND V0(4) <=
A0(2) THEN HPLOT V0(3), V0(4)
5040 RETURN

6000 REM ct_plot_circle
6010 PRINT "ct_plot_circle"
6020 AB = 6.28318 / V1(4)
6030 FOR I1 = 0 TO 6.28318 STEP AB
6040 V0(1) = V1(1) + COS(I1) * V1(3)
6050 V0(2) = V1(2) + SIN(I1) * V1(3)
6060 GOSUB 5000
6070 NEXT I1
6080 RETURN

7000 REM ct_plot_line
7010 PRINT "ct_plot_line"
7020 V0(1) = V5(1): V0(2) = V5(2)
7030 GOSUB 4000
7040 IF V0(3) < 0 THEN V0(3) = 0
7050 IF V0(3) > A0(1) THEN V0(3) = A0(1)
7060 IF V0(4) < 0 THEN V0(4) = 0
7070 IF V0(4) > A0(2) THEN V0(4) = A0(2)
7080 HPLOT V0(3), V0(4)
7090 V0(1) = V5(3): V0(2) = V5(4)
7100 GOSUB 4000
7110 IF V0(3) < 0 THEN V0(3) = 0
7120 IF V0(3) > A0(1) THEN V0(3) = A0(1)
7130 IF V0(4) < 0 THEN V0(4) = 0
7140 IF V0(4) > A0(2) THEN V0(4) = A0(2)
7150 HPLOT TO V0(3), V0(4)
7160 RETURN

8000 REM ct_koch
8010 IF RS(SP, 0) >= RN THEN RETURN
8020 PRINT "ct_koch = "; RS(SP, 0); " "; RS(SP, 1); " "; RS(SP, 2);
" "; RS(SP, 3); " "; RS(SP, 4)"
8030 RS(SP, 5) = RS(SP, 3) - RS(SP, 1) : REM difx
8040 RS(SP, 6) = RS(SP, 4) - RS(SP, 2) : REM dify
8050 RS(SP, 7) = RS(SP, 1) + RS(SP, 5) / 2 : REM dify
8060 RS(SP, 8) = RS(SP, 2) + RS(SP, 6) / 2 : REM dify
8070 RS(SP, 9) = -RS(SP, 6) : REM perpx
8080 RS(SP, 10) = RS(SP, 5) : REM perpy
8090 RS(SP, 11) = RS(SP, 7) + RS(SP, 9) / 3 : REM tipx
8100 RS(SP, 12) = RS(SP, 8) + RS(SP, 10) / 3 : REM tipy
8110 RS(SP, 13) = RS(SP, 1) + RS(SP, 5) / 3 : REM k0x
8120 RS(SP, 14) = RS(SP, 2) + RS(SP, 6) / 3 : REM k0y
8130 RS(SP, 15) = RS(SP, 3) - RS(SP, 5) / 3 : REM k1x
8140 RS(SP, 16) = RS(SP, 4) - RS(SP, 6) / 3 : REM k1y

8145 IF RS(SP, 0) < RN - 1 GOTO 8230
8150 V5(1) = RS(SP, 1): V5(2) = RS(SP, 2): V5(3) = RS(SP, 13): V5(4)
= RS(SP, 14)
8160 GOSUB 7000
8170 V5(1) = RS(SP, 13): V5(2) = RS(SP, 14): V5(3) = RS(SP, 11):
V5(4) = RS(SP, 12)
8180 GOSUB 7000
8190 V5(1) = RS(SP, 11): V5(2) = RS(SP, 12): V5(3) = RS(SP, 15):
V5(4) = RS(SP, 16)
8200 GOSUB 7000
8210 V5(1) = RS(SP, 15): V5(2) = RS(SP, 16): V5(3) = RS(SP, 3):
V5(4) = RS(SP, 4)
8220 GOSUB 7000

8230 REM line 0
8240 SP = SP + 1
8250 RS(SP, 0) = RS(SP - 1, 0) + 1
8260 RS(SP, 1) = RS(SP - 1, 1)
8270 RS(SP, 2) = RS(SP - 1, 2)
8280 RS(SP, 3) = RS(SP - 1, 13)
8290 RS(SP, 4) = RS(SP - 1, 14)
8300 GOSUB 8000
8310 SP = SP - 1
8320 REM line 1
8330 SP = SP + 1
8340 RS(SP, 0) = RS(SP - 1, 0) + 1
8350 RS(SP, 1) = RS(SP - 1, 13)
8360 RS(SP, 2) = RS(SP - 1, 14)
8370 RS(SP, 3) = RS(SP - 1, 11)
8380 RS(SP, 4) = RS(SP - 1, 12)
8390 GOSUB 8000
8400 SP = SP - 1
8410 REM line 2
8420 SP = SP + 1
8430 RS(SP, 0) = RS(SP - 1, 0) + 1
8440 RS(SP, 1) = RS(SP - 1, 11)
8450 RS(SP, 2) = RS(SP - 1, 12)
8460 RS(SP, 3) = RS(SP - 1, 15)
8470 RS(SP, 4) = RS(SP - 1, 16)
8480 GOSUB 8000
8490 SP = SP - 1
8500 REM line 3
8510 SP = SP + 1
8520 RS(SP, 0) = RS(SP - 1, 0) + 1
8530 RS(SP, 1) = RS(SP - 1, 15)
8540 RS(SP, 2) = RS(SP - 1, 16)
8550 RS(SP, 3) = RS(SP - 1, 3)
8560 RS(SP, 4) = RS(SP - 1, 4)
8570 GOSUB 8000
8580 SP = SP - 1
8590 RETURN
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 9/30/2026 12:57 PM, Alan Mackenzie wrote:

Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 9/25/2026 8:10 AM, Alan Mackenzie wrote:
[...]

Recursion in AppleSoft BASIC:

https://pastebin.com/raw/Effeg8cK

You've snipped all the context, you've given an unexplained URL, and
you've posted a quite long BASIC program [snipped] in a C group. This program is unexplained and severely lacking in comments. Does it have anything to do with the discussion about Ackermann's function?

What am I supposed to make of your post?

[ BASIC program snipped ]

Using a manual stack for recursion in AppleSoft BASIC.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 9/25/2026 8:10 AM, Alan Mackenzie wrote:
[...]

Recursion in AppleSoft BASIC:

https://pastebin.com/raw/Effeg8cK

You've snipped all the context, you've given an unexplained URL, and
you've posted a quite long BASIC program [snipped] in a C group. This
program is unexplained and severely lacking in comments. Does it have
anything to do with the discussion about Ackermann's function?

What am I supposed to make of your post?

[ BASIC program snipped ]
--
Alan Mackenzie (Nuremberg, Germany).

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.lang.c

On 30/09/2026 22:09, Chris M. Thomasson wrote:

On 9/30/2026 12:57 PM, Alan Mackenzie wrote:

Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:

On 9/25/2026 8:10 AM, Alan Mackenzie wrote:
[...]

Recursion in AppleSoft BASIC:

https://pastebin.com/raw/Effeg8cK

You've snipped all the context, you've given an unexplained URL, and
you've posted a quite long BASIC program [snipped] in a C group.-a This
program is unexplained and severely lacking in comments.-a Does it have
anything to do with the discussion about Ackermann's function?

What am I supposed to make of your post?

[ BASIC program snipped ]

Using a manual stack for recursion in AppleSoft BASIC.

I think we can all see that, but what relevance is it to the thread or
this group? If people had been wondering about whether "recursion" for algorithms must use "recursive function calls", you could have said "If
your language doesn't support recursive functions, or you don't want to
use them because of stack limits, you can emulate the stack in a data structure. I did so years ago in BASIC." The code itself is just
noise, and we have enough of that.

--- Synchronet 3.22a-Linux NewsLink 1.2