Are recursive algorithms an option?

[MorelSerge]

I'm trying to implement a recursive algorithm Wondering if this would actually work using Pequin, I first tried to implement the classic factorial algorithm listed below:

#include <stdint.h>

struct In {
  uint32_t n;
};

struct Out {
  uint32_t factorial;
};

void compute(struct In *input, struct Out *output){
  output->factorial = factorial(input->n);
}

uint32_t factorial(uint32_t n) {
  uint32_t ret;
  if (n == 0) {
    ret = 1;
  } else {
    ret = n * factorial(n - 1);
  }
  return ret;
}

This does not compile and throws a java.lang.StackOverflowError error.

I know you can implement factorial without using recursion, but is there any way to implement recursive algorithms using Pequin? Perhaps using Buffet to flatten the "loop" of the recursion?

[HarryR]

The problem is the number of recursions necessary is dependent on a variable input value, with the maximum possible being 2^32 recursions... this is obviously not practical or possible even if you use Buffet (or some other mechanism) to flatten the loop.

If you re-wrote it to be iterative, with a fixed bound on the loop, then it would be compatible with Pequin... but, using 32bit result values will be extremely limiting, and using 32bit input values isn't possible.

Alternatively you could use a hard-coded lookup table...

There are other methods of calculating the factorial with a few number of steps, see: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

[MorelSerge]

Thank you for the quick response.

I'm not looking for an efficient implementation of the factorial of a number necessarily. But rather I'm looking for a way to call a function recursively, possibly with a maximum number of recursions (say e.g. 20).

[maxhowald]

The Buffet transformer only works for loops. So, unless the compiler can statically bound your recursion at compile time, it won't work, unfortunately. I know it's not exactly what you're looking for, but here's what a factorial implementation in Pequin would look like using Buffet:

#include <stdint.h>

struct In {
  uint32_t n;
};

struct Out {
  uint32_t factorial;
};

uint32_t factorial(uint32_t n) {
  uint32_t ret;
  ret = 1;

  [[buffet::fsm(12)]]
  while(n) {
      ret = ret * n;
      n--;
  }
  return ret;
}

void compute(struct In *input, struct Out *output){
  output->factorial = factorial(input->n);
}

[MorelSerge]

Yes I understand, it would be great though if we could make the compiler statically bound the recursion because it allows for nice constructions.