保持計數在非尾遞歸

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