保持计数在非尾递归

Question

我正在写一个函数式语言（ML）的几个递归函数，并在其中几个是必须保持计数。我不允许使用尾递归或辅助函数。我应该如何保持计数？

例如，如果有一个问题需要删除字符串的第n个元素，那么在删除该元素之前，如何知道递归函数已被调用n次？

Answer 1

您可以将计数作为参数传递。我不知道ML，但在C风格的语言，它的完成，像这样：

void processTreeNode(Node* node, int count) { 

    foreach(Node* child in node->children) { 
     processTreeNode(child, count + 1); 
    } 
} 

第一个电话通常具有0或1值：

Node* root = ... 
processTreeNode(root, 1); 

注意上面的例子中实际上计数深度而不是迭代计数。

如果要计算时间的功能实际上已被呼叫的号码，您可以使用全局状态一个值（一个坏主意），或者通过引用传递线程局部值：

void processTreeNode(Node* node, int* count) { 

    (*count)++; 

    foreach(Node* child in node->children) { 
     processTreeNode(child, count); 
    } 
} 

与负责创造价值和参考第一个呼叫：这可以推广到其传递给所有功能的算法“上下文”对象

Node* root = ... 
int count = 0; 
processTreeNode(root, &count); 

要求 - 如果它是由引用进行传递，然后这样就避免了不必要的值 - 复制和堆栈空间分配，如以及正在线程安全提供没有其他线程有权访问它：

class MyAlgorithmContext { 
    int foo; 
    string bar; 
} 

Node* root = ... 
MyAlgorithmContext context; 
context.foo = 123; 
processTreeNode(root, &context);