Last active
April 4, 2022 21:23
-
-
Save Sebbyastian/9bf5551f915b2694c77e to your computer and use it in GitHub Desktop.
Ackermann function in recursive and non-recursive form
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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); | |
} | |
} | |
} |
Author
Sebbyastian
commented
Apr 4, 2022
via email
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:
***@***.***>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment