Can this implementation of Ackermann function be called tail recursive?

Question

I have written following code in C. Can we call it a tail recursive implementation?

#include <stdio.h>

int ackermann(unsigned int *m, unsigned int *n, unsigned int* a, int* len)
{
  if(!*m && *len == -1) {
    return ++*n;
  }
  else if(!*m && *len >= 0) {
    ++*n;
    *m = a[(*len)--];
  }
  else if(*n == 0) {
    --*m;
    *n = 1;
  } else {
    ++*len;
    a[*len] = *m - 1;
    --*n;
  }
  return ackermann(m, n, a, len);
}

int main()
{
  unsigned int m=4, n=1;
  unsigned int a[66000];
  int len = -1;

  for (m = 0; m <= 4; m++)
    for (n = 0; n < 6 - m; n++) {
      unsigned int i = m;
      unsigned int j = n;
      printf("A(%d, %d) = %d\n", m, n, ackermann(&i, &j, a, &len));
    }

  return 0;
}

If it is not tail-recursive please suggest ways to make it so. Any reference to a tail recursive version of Ackermann would be nice in C/C++/Java or non-functional programming language.

Please mark the corresponding answer as _solution_ if it solves the problems from your question, this way future readers can easily identify the solution. — Ling Zhong, Oct 19 '15 at 15:27

Sylwester · Answer 1 · 2015-10-20T09:24:15.010

4

Your function uses a data structure to do it's backtracking so while it is a tail recursive function it definitely isn't a simple recursive or iterative process. The array a takes the role as a recursion stack. You could write out the recursive call alltogether:

int ackermann(unsigned int *m, unsigned int *n, unsigned int* a, int* len)
{
  while (*m || *len != -1) {
      if(!*m && *len >= 0) {
        *n++;
        *m = a[(*len)--];
      } else if(*n == 0) {
        *m--;
        *n = 1;
      } else {
        ++*len;
        a[*len] = *m - 1;
        *n--;
      }
  }
  return ++*n;
}

Still without any recursive call I consider this a recursive process.

edited Oct 20 '15 at 09:24

answered Oct 19 '15 at 14:57

Sylwester

47,942
4
47
79

[every recursion can be converted into iteration](http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) by simulating the recursion stack (in general, on the heap - the question becomes, the size of this space that is needed). -- `unsigned int a[66000];` looks like it can be used to simulate the recursion stack. Of course for bigger `n` and `m` the reserved space will have to grow much much bigger, if it *is* a proper Ackermann function. – Will Ness Oct 19 '15 at 15:14
1

and the growing space that is used, corresponds with the time needed to complete the calculation. which was, I think, the point to this function -- that it grows very very *very* fast / large. as a comment on that question says, the transformation is about "converting stack variables into a (simulated) stack of variables". :) – Will Ness Oct 19 '15 at 15:22
1

@WillNess You're talking about recursive function versus iterative function, while I'm talking about recursive process vs iterative process. If you make a iterative loop and grow a data structure to do some kind of backtracking it is *still a recursive process*. Likewise if you use tail recursion in a TCO language it is an iterative process even if it's using recursion. The recursion that can be made iterative, like fibonacci, becomes iterative. Ackermans function won't. – Sylwester Oct 19 '15 at 17:44
`Tail recursion == iterative process` is false. tail recursion just means code is equivalent to a loop; it doesn't preclude the code mutating a store, in a loop. tail recursion is a syntactic trait. there's no backtracking there, the data store gets filled up. the point to Ackermann function was, this store grows much faster than exponential law, AFAIR. whether in implicit stack or explicitly, it doesn't matter. yes we can call it a "recursive process", the question is about it being "tail recursive" though. – Will Ness Oct 19 '15 at 20:39
@WillNess Why I chose that array is because beyond A(4, 1) it is too big to be held by C data type. And the value of A(4,1) is 65k+ so I know that there will be no more than those many calls. Although, a smaller array will also work and yes it has been used like a stack. A dynamic stack will be better if we need bigger values. – Shiv Oct 20 '15 at 02:44
@Sylwester Ackermann function has nested recursion as you know. I have implemented only outer level in terms of stack the inner level is still recursive. – Shiv Oct 20 '15 at 02:44
@WillNess You are right. I was actually contradicting myself as tail recursion + imlpicit stack / nested closures is definitely a recursive process. Embarrassing. – Sylwester Oct 20 '15 at 09:26
@Sylwester I skimmed through Wikipedia's corecursion/anamorphism/catamorphism articles, it seems the proper terminology is "primitive recursion" vs. "recursion"; I've seen also "general recursion" but couldn't find the specifics about it. not in Wikipedia at least, and I'm not going to pay $45 per article on various scientific journals sites that Google finds, :) so don't really know. maybe ask on Reddit? your code is a loop and calling it "recursive process" looks like a stretch even if that's what SICP would call it. :) maybe call it "non-primitive recursion"? but is it a proper term? dunno. – Will Ness Oct 20 '15 at 21:30
@WillNess The problem is that we often talk about recursion as a method of getting things done while on the machine level it really doesn't exist. Its really not that interesting if the code uses a method or not. Using the SICP "process" is the closest I've come and iterative are constant space while recursive isn't. The recursive definition of `ackerman` is much nicer to look at than the code on this page so a perfect world would have compilers that optimized that rather than needing this manual optimization. – Sylwester Oct 20 '15 at 23:50
@Sylwester "on the machine level it really doesn't exist" exactly. "iterative process" sounds nice, but "recursive", without the actual recursion, not so much. maybe call it "non-iterative process"; or talk about "simple"/"complex" processes... about compilers, couldn't agree more. – Will Ness Oct 21 '15 at 00:32
@sylwester, indeed, and compilers can do TCO, but need some help. The code on this page is not a good example. Continuation Passing Style would be a better way to show TCO with Ackerman, and the need data structure is than automatic. Ackerman can be represented in a functional language, or any language that supports higher order functions, using CPS (but it'll still need beyond-the-age-of-universe time to complete on most input). – Abel Apr 20 '20 at 12:00
Here's an example that uses CPS, with just a few clean lines: https://rosettacode.org/wiki/Ackermann_function#F.23 – Abel Apr 20 '20 at 12:09
@Abel F#? This is a C question. Yes. CPS will make the code tail recursive, but it is still a recursive process since the callbacks gets nested. Instead of deep stacks you get deep nesting of heap allocated closures. Many Scheme systems do this on all code which means instead of getting stack overflow the system fails when there is no heap memory left. – Sylwester Apr 20 '20 at 22:11
@sylwester, haha, you're right, not sure why I linked the F# code. In C you could achieve the same idea with function pointers. Either way, the point remains the same, as you clearly summarized in your last comment :) – Abel May 10 '20 at 11:31

score 1 · Accepted Answer · answered Oct 19 '15 at 14:57

1

By definition your ackermann function is a tail-recursive function as you're directly returning the result of the recursive case. Since no further logic depends on the result of your recursive call, the compiler can safely apply tail-recursion optimization.

answered Oct 19 '15 at 14:57

Ling Zhong

1,744
14
24

Thanks for the confirmation. – Shiv Oct 19 '15 at 15:03
No problem :) Kudos to you for leveraging this optimization. Extra stack frames created due to recursive calls are very expensive. – Ling Zhong Oct 19 '15 at 15:09

Can this implementation of Ackermann function be called tail recursive?

2 Answers2

Linked