Übergeben einer Variablen durch Verweis auf eine wiederkehrende Funktion

Question

Ist ein Argument für eine Funktion, die eine Referenz auf die Variable static in rekursive Funktion ist? Unten ist eine Funktion zum Finden der kleinsten Wurzel in einer BST.

int findNode(TreeNode* root, int &k) { 
    if(root == NULL) 
     return -1; 
    // We do an inorder traversal here. 
    int k1 = findNode(root->left, k); 
    if(k == 0) return k1; // left subtree has k or more elements. 
    k--; 
    if(k == 0) return root->val; // root is the kth element. 
    return findNode(root->right, k); // answer lies in the right node. 
} 

int kthsmallest(TreeNode* root, int k) { 
    return findNode(root, k); // Call another function to pass k by reference. 
} 

Die Funktion kthsmallest der k-ten kleinsten Knotens Wert zurückgibt.

Knoten Definition:

struct TreeNode { 
    int val; 
    TreeNode* left; 
    TreeNode* right; 
} 

Meine Frage ist, warum k durch Referenz übergeben wird.

Answer 1

Die Bedeutung von k ist für den Gesamtalgorithmus relevant, nicht der individuelle Aufruf an findNode. Es ist wie ein Countdown-Timer; Der Algorithmus wird beendet, wenn k 0 erreicht. Alle rekursiven Aufrufe tragen zu demselben Countdown bei.

Das Übergeben eines Verweises auf eine Variable in einem aufrufenden Bereich löst ein ähnliches Problem wie static, aber es wird allgemein als eine überlegene Technik in der Softwareentwicklung angesehen. Globals (z. B. static) begrenzen die Skalierbarkeit eines Programms.

Die Moral der Geschichte ist nicht, Namen wie k zu verwenden. Nennen Sie es so etwas wie remaining_nodes.