Re: MISRA C

From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: MISRA C
Date	2026-10-03 23:55 +0100
Organization	A noiseless patient Spider
Message-ID	<87o6da9yyi.fsf@bsb.me.uk> (permalink)
References	(13 earlier) <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>

Show all headers | View raw

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!

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

In an imaginary C with unbounded integers, you can do it with a couple
of VLAs at the top of the function.

-- 
Ben.

Thread

MISRA C (was: buckle-up ....) Alan Mackenzie <acm@muc.de> - 2026-09-25 10:01 +0000
  Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 14:52 +0200
    Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 13:48 +0000
      Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-25 16:39 +0200
        Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 15:10 +0000
          Re: MISRA C bart <bc@freeuk.com> - 2026-09-25 16:57 +0100
          Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 11:42 -0700
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-25 20:21 +0000
              Re: MISRA C Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-09-25 14:05 -0700
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-26 08:43 +0200
                Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-26 17:55 +0000
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-03 23:55 +0100
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-04 16:10 +0200
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 01:22 +0100
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-05 07:59 +0200
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:23 -0700
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-05 01:24 -0700
                Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 09:02 +0000
                Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-10-05 12:07 +0200
                Re: MISRA C Ben Bacarisse <ben@bsb.me.uk> - 2026-10-05 15:29 +0100
                Re: MISRA C antispam@fricas.org (Waldek Hebisch) - 2026-10-05 20:29 +0000
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:13 -0700
                Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-10-06 22:14 -0700
          Re: MISRA C Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-09-27 10:52 -0700
          Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 13:08 +0200
            Re: MISRA C bart <bc@freeuk.com> - 2026-09-28 13:07 +0100
            Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-28 14:08 +0200
              Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:28 +0200
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-28 12:17 +0000
              Re: MISRA C Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-09-28 14:40 +0200
          Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 10:21 -0700
            Re: MISRA C Alan Mackenzie <acm@muc.de> - 2026-09-30 19:57 +0000
              Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-30 13:09 -0700
                Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-10-01 08:47 +0200
                Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-10-01 15:18 -0700
      Re: MISRA C Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2026-09-27 04:58 +0800
  Re: MISRA C David Brown <david.brown@hesbynett.no> - 2026-09-25 17:02 +0200
  Re: MISRA C "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2026-09-26 15:37 -0700

csiph-web