Ackermann function in recursive and non-recursive form

ack.c

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int ack_recursive(int m, int n) {
    if (m == 0) {
        return n + 1;
    }

    if (n == 0) {
        return ack_recursive(m - 1, 1);
    }

    return ack_recursive(m - 1, ack_recursive(m, n - 1));
}

int ack_nonrecursive(int m, int n, int *status) {
    int value[n];
    size_t size = 0;

    for (;;) {
        if (m == 0) {
            n++;
            if (size-- == 0) {
                *status = EXIT_SUCCESS;
                break;
            }
            m = value[size];
            continue;
        }

        if (n == 0) {
            m--;
            n = 1;
            continue;
        }

        size_t index = size++;
        value[index] = m - 1;
        n--;
    }

    return n;
}

int main(void) {
    for (int m = 0; m < 2; m++) {
        for (int n = 0; n < 2; n++) {
            int status;
            assert(ack_recursive(m, n) == ack_nonrecursive(m, n, &status) && status == EXIT_SUCCESS);
        }
    }
}

thanks for sharing!

This line "int value[n];" is not correct, as you would need way larger array than size n.

This line "int value[n];" is not correct, as you would need way larger array than size n.

We can put assertions before each value access to ensure they're in range. Observe the assertions passing during runtime, thus proving that n is the correct size to use. If it weren't, we'd see an assertion failure kind of like this.

thanks for sharing :D

can you please explain the non-recursive version?

Which element/s are unclear to you? Perhaps the most common hurdle is realising that recursion gives you a stack, which pushes and pops implicitly as the function enters and returns... whereas in the non-recursive function we must provide our own stack (or equivalent) and push/pop from it using other mechanisms.

…

On 5 Mar 2020 03:08, "Sam-Hack-King" ***@***.***> wrote: can you please explain the non-recursive version? — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://gist.github.com/9bf5551f915b2694c77e?email_source=notifications&email_token=ABMNBDRF3B4H5RBZVB2GCHTRF2DI5A5CNFSM4LBNXCNKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAGDKGM#gistcomment-3200102>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABMNBDVBZIMMAXDI6YX2KU3RF2DI5ANCNFSM4LBNXCNA> .

This line "int value[n];" is not correct, as you would need way larger array than size n.

We can put assertions before each value access to ensure they're in range. Observe the assertions passing during runtime, thus proving that n is the correct size to use. If it weren't, we'd see an assertion failure kind of like this.

The only reason this array size works is because your test cases are way too small. for m and n less than 2, the function barely does anything, so it doesn't matter the size of the array. If you increased the test cases to m=3, n = 5, then the assertion fails. For larger inputs, the stack size required increases dramatically.

It doesn't follow. Your first claim is that an array with `n` objects isn't large enough, and now you're clutching at straws by stating that for large values of `n` there may be some environmental limitations that cause it to misbehave Well, duh! For large values of `n`, this is a problem because resources are finite. You cannot hope to allocate memory for a number that's too large to store in your computers RAM, and this is to what end you clutch at straws. I could adapt my implementation of C to fail if you use automatic variables that are longer than 0 but shorter than 2, the implementation would be compliant in the eyes of the standard but the rationale assumes implementations are meant to be useful. While we talk about usefulness, this code wasn't written to be productive; it was written to demonstrate that the typical Ackermann recursive algorithm can be written procedurally, and that's all... an academic piece, if you like. For that purpose most standard implementations will be fine, so unless you intend to justify that `n` (or the stack, whatever that means) is still too small to serve the academic purpose of demonstration, we're done here.

…

On Tue, 5 Apr 2022, 4:46 am searsm8, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ This line "int value[n];" is not correct, as you would need way larger array than size n. We can put assertions before each value access to ensure they're in range. Observe the assertions passing during runtime <https://ideone.com/r58OOG>, thus proving that n is the correct size to use. If it weren't, we'd see an assertion failure kind of like this <https://ideone.com/9AdINp>. The only reason this array size works is because your test cases are way too small. for m and n less than 2, the function barely does anything, so it doesn't matter the size of the array. If you increased the test cases to m=3, n = 5, then the assertion fails. For larger inputs, the stack size required increases dramatically. — Reply to this email directly, view it on GitHub <https://gist.github.com/9bf5551f915b2694c77e#gistcomment-4121100>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABMNBDRHWOOYRQNDOPPAJELVDM2JJANCNFSM4LBNXCNA> . You are receiving this because you authored the thread.Message ID: ***@***.***>