问题是解决方案在什么时候停止被认为是递归的,即使实现的基本算法是递归的？

为了完整起见,所有情况都使用以下函数：

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];
}

情况1：清除递归

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,used);
  return 0;
}

案例2：硬编码展开

请注意,函数在任何时候都不会调用自身或任何直接或间接调用者

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);
  }
}

案例3：迭代版本

请注意,没有调用任何函数(除了明显显示),但它是相同的算法

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
    }
  }
}

那么,CASE 1只是递归吗？或者我们还包括CASE 2甚至CASE 3？