什么定义了递归函数？
什么定义了递归函数？
提问于 2015-08-19 19:32:42
问题是，在什么时候解决方案停止被认为是递归的，即使实现的基本算法是递归的？
为了完整起见，所有情况下都使用下列功能：
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？
Stack Overflow用户
发布于 2015-08-19 21:23:19
递归一词在不同的上下文中使用。您有递归函数的简单定义，其中一个函数直接间接地调用自己，但是在计算机科学中，您也谈到了一个过程。
迭代过程基本上是一个原始的递归函数。所有函数都可以通过迭代或尾递归来定义。示例：
int test (int x)
{
return x + 1;
}
int factorial(int x)
{
int a = 1;
while( x > 1 ) {
a *= x;
}
return a;
}
int factorial_aux(int x, int a)
{
return x == 0 ? a : factorial_aux(x-1, a*x);
}递归过程是一个过程，它总是需要某种类型的数据结构来保存数据，而它正在处理中，以便进行跟踪。这方面的一个例子可能是树遍历：
Node* search(Node* tree, int needle) {
if( tree == NULL || tree->value == needle )
return tree;
else
return search(tree->left, needle) || search(tree->right, needle);
}
Node* search(Node* tree, int needle) {
Stack<Node *> stack;
if( tree )
stack.push(tree);
while ( stack.empty() == false ) {
Node* n = stack.pop();
if( n->value == needle )
return n;
if( tree->right != NULL )
stack.push(tree->right);
if( tree->left != NULL )
stack.push(tree->left);
}
return NULL;
}以上两个都是递归过程。一个使用递归函数，另一个使用循环迭代函数，这一事实并不改变系统堆栈或显式堆栈将随着进程从根进一步访问节点而增长的事实。
CPU通常不支持大部分这些东西，所以编译器需要通过使用原始指令、推送和清理堆栈来传递参数来进行大量的“模拟”。因此，在这种情况下，递归函数通常是一个具有不断增长的堆栈的迭代过程。
因此，要回答你的问题：
- 进程的：当所使用的空间为常数时，
- 函数的：当不可能进行直接或间接的自调用时，
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32104129
复制相关文章
相似问题
腾讯云开发者
