Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: MISRA C
Date: Mon, 05 Oct 2026 01:23:07 -0700
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <86ik3gmu8k.fsf@linuxsc.com>
References: <11822bi$39m36$1@dont-email.me> <118pkkd$3gajb$1@dont-email.me> <118q3np$3e19p$2@dont-email.me> <118q63q$3l59m$1@dont-email.me> <118qftr$3nc7i$1@dont-email.me> <119473t$33192$1@dont-email.me> <119493r$33m1o$1@dont-email.me> <1194c7i$34ldb$2@dont-email.me> <1194mqo$37fnf$3@dont-email.me> <1195gqh$23uj$1@news.muc.de> <1195qr8$2aem2$1@dont-email.me> <1195u2r$16ah$1@news.muc.de> <119612d$2aem2$2@dont-email.me> <11962u0$16ah$2@news.muc.de> <1196fb8$3rdj2$1@kst.eternal-september.org> <1196l3v$1b0$1@news.muc.de> <1196nn7$3upk9$1@kst.eternal-september.org> <1197piq$8k7p$1@dont-email.me> <87o6da9yyi.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 05 Oct 2026 08:23:08 +0000 (UTC)
Injection-Info: dont-email.me; logging-data="762729"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX184Iilav3VeUSUlOnrPzLfyR4u9vTInC28="; posting-host="9c7cd6cf42d57b8cdde7cd2072fc92b7"
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:PlfwqKn8duy4lWiBolk6SbRrKJs= sha1:zdDktf2QT0eDHbW1V7ysIy/g9m8= sha256:a66F1HrBjE2rJ+tBF10NKO1l895qs/Fkd01kEU9FgOU= sha1:o96rdby32RirH+5pa++trSfSwRk= sha256:aUIuh+p/Ac3mrALYyLMuoJBmsIOdz0d623BjhSq8FeQ=
Xref: csiph.com comp.lang.c:402699

Ben Bacarisse <ben@bsb.me.uk> writes:

> Sorry I'm jumping in here.  I don't read Usenet much these days but this
> got me going.
>
> David Brown <david.brown@hesbynett.no> writes:
>
>> 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.
>
> Hmm...  This is likely to confuse people.  You can calculate A(m,n)
> using O(m) extra space.  You can pre-allocate the space you need
> before starting the calculation.  (Aside: this disregards the space
> needed to store the numbers.  A(m, n) grows so large that you need
> extra space just to store the integers, but that complicates the
> discussion and I think everyone has been ignoring it in this thread
> anyway.)
>
> A carefully written recursive version will also use only O(m)
> stack, but here we get into problems of definition.  Given that
> there is an iterative version that needs only O(m) extra storage
> there is obviously a trivial recursive version of that function
> that, say, just pointlessly calls itself once!

I don't see what you're getting at here.  The idea that A(m,n)
can be computed with only O(m) space, for any n, goes against
both my intuition and what I remember from my recursive function
theory course (quite a long time in the past now).  At the very
least it seems to require a radically different formulation of
how the Ackermann function is defined.  Can you elaborate how,
for example, A(m,n) can be computed by a recursive function with
O(1) local variables but a call depth that never exceeds O(m)?

By the way, I think I know what you're getting at with extra
storage needed to store the numbers, but we need to be careful
here.  If we are allowed variables that hold arbitrary precision
integers then surely any computable function can be calculated
using only O(1) such variables.