什么定义了递归函数？
问题是，在什么时候解决方案停止被认为是递归的，即使实现的基本算法是递归的？
为了完整起见，所有情况下都使用下列功能：
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？
回答 4
Stack Overflow用户
发布于 2015-08-19 19:46:43
函数的递归定义与其递归实现(或算法)有区别。
函数可以以递归的方式进行数学定义，但是计算此函数的算法(即实现)很可能是非递归的，反之亦然。
请注意，对于同一个函数，可能有不同的数学定义和不同的算法。
在您提供的示例中，很明显，案例1--实现是递归的，而案例2和案例3--实现不是递归的，不管函数的数学定义是递归的还是非递归的。
为了将其保留在问题的范围内，我有意不触及直接/间接递归，也没有触及一些仅通过递归表示迭代的纯函数式语言。
Stack Overflow用户
发布于 2015-08-19 22:40:49
当在任何时候，对于任何输入，在激活链中没有出现任何函数的多个实例时，解决方案就不再是递归的:没有重新输入任何函数。
“展开递归”是否递归？这取决于我们是在谈论展开解决方案所依据的概念，还是它的实现。
显然，实现不是递归的。
显然，函数的展开副本是基于递归实现的机械重复，解决方案仍然表示该解决方案的某些方面；当您查看代码时，很明显可以将其回滚到递归实现中。我们还可以根据算法的递归描述验证该解决方案；也就是说，以递归算法的描述为指导，我们可以很容易地说服自己，未展开的实现是正确的还是错误的。
很明显，展开的代码就是:递归解决方案的展开实现。我们不能否认与递归规范的连接，但是我们必须承认递归没有发生。
Stack Overflow用户
发布于 2015-08-19 20:55:56
阿列克斯-谢斯特罗夫给出的答案只是为了稍微扩展一下。显式递归通常是昂贵的，并且取决于用例，它有溢出堆栈的风险，这就是为什么在实践中通常通过与您类似的转换来避免这种情况。
考虑一个尾递归函数.跟听起来一样，尾递归函数是在函数调用中不保留任何状态的函数(递归调用位于末尾)。编译器通常会将这些实现为迭代代码，因为这是一个简单的转换。
递归是描述函数的一种非常简洁的方法，这就是为什么使用它来描述大量函数的原因(即Fibonacci数)。但是，在实践中，通常更好的做法是迭代地重新表述它们。
用斐波纳契数字..。
F(0) = 0
F(1) = 1
F(N) = F(N-1) + F(N-2)所以，通常在C++中它可以用.
size_t fib(size_t n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
return fib(n - 1) + fib(n - 2);
}尽管它效率很低(重新计算值、在调用堆栈上存储数据等等)。一种优化是回溯函数调用。但是，实际值可以自下而上地构造，所以最好是简单地迭代地重新表示它。
size_t fib(size_t n) {
size_t p = 0, c = 1;
if (n == 0)
return 0;
while (n--) {
size_t t = c;
c = p + c;
p = t;
}
return c;
}为了好玩，哈斯克尔也是这样.
fib n = fibs !! n
where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)https://stackoverflow.com/questions/32104129
复制相似问题
腾讯云开发者
