c++ - 什么定义了递归函数？

Question

除了提出的简单问题 here 并基于 this评论

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

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

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, 0, 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？

Answer 1

函数的递归定义与其递归实现(或算法)之间存在差异。

一个函数可以用递归的方式在数学上定义，但是计算这个函数的算法(即实现)很可能是非递归的，反之亦然。

请注意，同一个函数可能有不同的数学定义和不同的算法。

---

在您提供的示例中，很明显CASE 1-实现是递归的，而CASE 2-和CASE 3-实现 em> 不是递归的，无论函数的数学定义是否递归。

---

附言为了将其保留在问题的范围内，我有意没有触及直接/间接递归，也没有触及一些仅通过递归表达迭代的纯函数式语言。