非末尾再帰でカウントを続ける

Question

私はいくつかの再帰関数を関数言語（ML）で書いていますが、それらのいくつかではカウントを維持する必要があります。私は末尾の再帰関数やヘルパー関数を使用することはできません。私はどのようにカウントするべきですか？

たとえば、文字列のn番目の要素を削除する問題が発生した場合、その要素を削除する前に再帰関数がn回呼び出されたことをどのように知ることができますか？

Answer 1

パラメータとしてカウントを渡すことができます。実際にカウント

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

上記の例に注意してください。私はMLを知っているが、それはそうのように行うのCスタイルの言語ではありません：

void processTreeNode(Node* node, int count) { 

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

最初の呼び出しは通常0または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); 

スレッドセーフです