How to improve recursive function in C?-CodePudding

i have a program with various recursive functions. I now need to optimize the code to run the program faster: i checked with profiler and, a part from the biggest function with lots of checks, i have two functions that require a lot of time every run. One (Unmarked_Nodes) is like this:

typedef struct node* tree;

struct node{
char* data;
tree left;
tree right;
int marker;
};

static int remaining = 0;

int main(){
...
}

int Unmarked_Nodes(tree root) {
  if (root != NULL) {
    Unmarked_Nodes(root->left);
    if (root->marker == 0)
      remaining  ;
    Unmarked_Nodes(root->right);
  }
return remaining;
}

The other is similar but instead of the if cycle it has a printf of data. The other, however, is faster than this... why? Or instead: how can i improve the code to make it run faster? Thanks in advance

CodePudding user response：

Candidate improvements: might help a little although answer remains O(n).

Recurse less often

Loop inside the function for one of the children.

Avoid global

Simply not needed.

Use const

No so much a speed improvement, yet allows for use with constant data.

Avoid hiding pointers

int Unmarked_Nodes(const struct node *root) {
  int remaining = 0;
  while (root != NULL) {
    remaining  = Unmarked_Nodes(root->left);
    if (root->marker == 0) {
      remaining  ; 
    }
    root = root->right;
  } 
  return remaining;
}

Perhaps only recurse when both children are non-NULL. Test null-ness at the end of the loop since it is initially false for all recursive entry.

static int Unmarked_Nodes2r(const struct node *root) {
  int remaining = 0;
  do {
    if (root->marker == 0) {
      remaining  ; 
    }
    if (root->left) {
      if (root->right) {
        remaining  = Unmarked_Nodesr(root->right);
      }
      root = root->left;
      // continue;  // Could skip loop test.
    } else {
      root = root->right;
    }
  } while (root);
  return remaining;
}

int Unmarked_Nodes2(const struct node *root) {
  return root ? Unmarked_Nodes2r(root) : 0;
}

CodePudding user response：

In the absence of more information, it would seem that you likely "visit" the tree three times: once for 'marking' nodes (for whatever purpose), once to 'print' marked (or unmarked) nodes, and once more to reset those marks.

Presuming that 'marked nodes' are the interesting ones, consider using a dynamic array of pointers (malloc/realloc in suitable increments) to build a list of only those nodes, print from that list (no 2nd tree traversal), then free() the list (no 3rd tree traversal).

You wouldn't need to 'mark/unmark' anything. Interesting nodes added to the suggested list mean that those nodes are 'marked', and 'unmarked' when the list is erased.

You may need to consider if 'marking' may encounter unwanted duplicates.

Another suggestion is to consider transforming the tree into a list once it is filled. Then, use conventional binary search of that list to mark 'nodes', and a sweep through to erase marks (presuming the same list is to be reused multiple times.