what defines a recursive function?

Question

Beyond the simple question asked here And based on this comment

The question is at what point does a solution stop being considered recursive, even if the base algorithm implemented is recursive?

For completeness, the following functions are used by all cases:

int counter=0;
int reps=0;

void show(int x)
{
#ifdef OUTPUT
    printf("==============>>> %d <<<\n", x);
#endif
    counter+=x;
    ++reps;
}

int bit_val(unsigned int v)
{
  static const int MultiplyDeBruijnBitPosition2[32] =
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  return MultiplyDeBruijnBitPosition2[(unsigned int)(v * 0x077CB531U) >> 27];
}

CASE 1: Clear recursion

void uniq_digitsR(int places, int prefix, int used) {
  if (places==1) {
    show(prefix*10+bit_val(~used));
    return;
  }
  int base=prefix*10;
  unsigned int unused=~used;
  while(unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digitsR(places-1, base+bit_val(bit), used|bit);
  }
}

int uniq_digits9() {
  unsigned int used=~((1<<10)-1); // set all bits except 0-9
  used |= 1;                      // unset 0
  uniq_digitsR(9, 0, used);
  return 0;
}

CASE 2: Hardcoded Unrolling

Note that at no time does a function call itself or any direct or indirect caller

void uniq_digits1(int prefix, unsigned int used) {
  show(prefix*10+bit_val(~used));
}

void uniq_digits2(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits1(base+bit_val(bit), used|bit);
  }
}

void uniq_digits3(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits2(base+bit_val(bit), used|bit);
  }
}

void uniq_digits4(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits3(base+bit_val(bit), used|bit);
  }
}

void uniq_digits5(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits4(base+bit_val(bit), used|bit);
  }
}

void uniq_digits6(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits5(base+bit_val(bit), used|bit);
  }
}

void uniq_digits7(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits6(base+bit_val(bit), used|bit);
  }
}

void uniq_digits8(int prefix, unsigned int used) {
  int base=prefix*10;
  unsigned int unused=~used;
  while (unused) {
    unsigned int diff=unused & (unused-1);
    unsigned int bit=unused-diff;
    unused=diff;
    uniq_digits7(base+bit_val(bit), used|bit);
  }
}

void uniq_digits9() {
  unsigned int used=~((1<<10)-1); // set all bits except 0-9
  used |= 1;                      // unset 0
  for (int i = 1; i < 10; i++) {
    unsigned int bit=1<<i;
    uniq_digits8(i,used|bit);
  }
}

CASE 3: Iterative Version

Note that no functions are called (aside from obviously show) but it is the same algorithm

void uniq_digits(const int array[], const int length) {
  unsigned int unused[length-1];                    // unused prior
  unsigned int combos[length-1];                    // digits untried
  int digit[length];                                // printable digit
  int mult[length];                                 // faster calcs
  mult[length-1]=1;                                 // start at 1
  for (int i = length-2; i >= 0; --i)
     mult[i]=mult[i+1]*10;                          // store multiplier
  unused[0]=combos[0]=((1<<(length))-1);            // set all bits 0-length
  int depth=0;                                      // start at top
  digit[0]=0;                                       // start at 0
  while(1) {
    if (combos[depth]) {                            // if bits left
      unsigned int avail=combos[depth];             // save old
      combos[depth]=avail & (avail-1);              // remove lowest bit
      unsigned int bit=avail-combos[depth];         // get lowest bit
      digit[depth+1]=digit[depth]+mult[depth]*array[bit_val(bit)]; // get associated digit
      unsigned int rest=unused[depth]&(~bit);       // all remaining
      depth++;                                      // go to next digit
      if (depth!=length-1) {                        // not at bottom
        unused[depth]=combos[depth]=rest;           // try remaining
      } else {
        show(digit[depth]+array[bit_val(rest)]);    // print it
        depth--;                                    // stay on same level
      }
    } else {
      depth--;                                      // go back up a level
      if (depth < 0)
        break;                                      // all done
    }
  }
}

So, is just CASE 1 recursive? Or do we also include CASE 2 or even CASE 3?

Answer 1

There's a difference between a recursive definition of a function, and its recursive implementation (or algorithm).

A function may be mathematically defined in a recursive manner, but an algorithm (i.e. implementation) which calculates this function may well be non-recursive, and vice versa.

Note that there may be different mathematical definitions and different algorithms for the same function.

---

In the examples you've provided, it's totally obvious that CASE 1-implementation is recursive, while CASE 2- and CASE 3-implementations are not recursive, regardless if the mathematical definition of the function was recursive or not.

---

P.S. to keep it in the question's scope, I intentionally didn't touch direct/indirect recursion, nor some pure functional languages which express iterations through recursion only.