Collecting data in recursion function in C

Question

I am writing an huffman algorithm and I got problem with a collecting data in recursion function. It means I have a recursion function which generates codes from tree, but I would like to have them in array (this allow me processing data later). I wrote the function

void save_code(HuffNode** array, int pos, HuffNode *node, char * table, int depth)
{
  if(node->left == NULL){
    printf("%d - %c > ", pos, node->sign);

    array[pos]->sign = node->sign;
    strcpy(array[pos]->code, table);

    puts(table);
    // save to global table
  }
  else {
    table[depth] = '0';
    save_code(array, pos + 1, node->left, table, depth + 1);
    table[depth] = '1';
    save_code(array, pos + 1 , node->right, table, depth + 1);
  }
}

The biggest problem I have with variable pos, I thought if I can increment the pos variable (like in loop for),so I would be able to save it in variable array at position pos. The whole program is here: https://github.com/mtczerwinski/algorithms/blob/master/huffman/huffman.c

Edit: I ask myself if global variable can solve a problem - after a few moments of coding - the answer is positive.

int pos = 0; // global variable
void save_code(HuffNode** array, HuffNode *node, char * table, int depth) {
  if(node->left == NULL){
    array[pos]->sign = node->sign;
    strcpy(array[pos]->code, table);
    pos++;
  }
  else {
    table[depth] = '0';
    save_code(array , node->left, table, depth + 1);
    table[depth] = '1';
    save_code(array, node->right, table, depth + 1);
  }
}

I would like to ask how to collect data in recursion function between calls. What are other ways to solve problem like this one.

Bernhard Barker · Accepted Answer · 2014-04-02 18:31:46Z

Pass it by pointer:

void save_code(..., int *pos)
{
  // ...
  // use and modify (*pos) as you desire
  // ...
  save_code(..., pos);
  // ...
}

This is a good approach, except that it doesn't look too pretty - you have an additional parameter for each recursive call and you have to use *pos instead of pos.

Pass and return it:

int save_code(..., int pos)
{
  // ...
  // use and modify pos as you desire
  // ...
  pos = save_code(..., pos);
  // ...
  return pos;
}

I wouldn't really recommend this (at least not above pass by pointer) as you'd return and pass a value, which seems unnecessary, since you only need to do one of those.

You also can't use this approach with multiple values, but it's easy to fix by using a struct, although if the function already returns something, this gets quite a bit messier.

And, for completeness, global variable:

int pos = 0; // global variable
void save_code(...)
{
  // ...
  // use and modify pos as you desire
  // ...
  save_code(...);
  // ...
}

This has the disadvantage of having a pos variable floating around in global scope, but this could, in many cases, fairly easily be fixed by making it static so it's limited to one file, or, in the OOP world (e.g. in C++), one could hide this as a private class member.

Using a global variable would be a problem with multi-threading (i.e. multiple calls to the function executing at the same time).

I chose to favour brevity above completeness with regard to my code samples - I hope they're readable enough.

Collectives™ on Stack Overflow

Collecting data in recursion function in C

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related