List parameters in recursive calls (C)

I开发者_开发问答'm designing a recursive algorithm :

int f(int[] a, int[] b){
----changing a here
----changing b here
f(a,b)
----writing a here
----writing b here
}

I know all arrays are pointers so this code should be problematic. It'll write the final values of a and b after all the recursive calls finished. I dont want that to happen.

What should I do to pass that array to recursive calls as regular "pass by value"?

PS: Arrays may be dynamically allocated or resized etc anywhere in recursive calls.

I will assume that int f(int[] a, int[] b) is a typo: it should be int f(int a[], int b[]).

First of all, arrays and pointers are different. Under many circumstances, the name of an array "decays" to a pointer to its first element, but not always. Otherwise, sizeof a, for an array a wouldn't "work".

Secondly, let's ignore recursion for a moment. Let's also make the function prototype simpler:

int g(int *a);

(I changed int a[] to int *a, because in this context, the name of an array is equivalent to a pointer.)

Now, you say that you may "dynamically allocate or resize" the array in the function call. Since everything is passed by value in C, a dynamic allocation or resizing of a inside g() cannot be seen by the caller: the caller would still have the old value of a. But more importantly, if the "original" type of a was an array, i.e., the caller had code like:

int data[SIZE];
g(data);

then trying to resize data in g() is bad, because the parameter specified in the call wasn't dynamically allocated to begin with. You can only dynamically resize something that was the result of malloc(), calloc(), or realloc().

So, there are two problems even with this simple definition:

• If g() has to dynamically resize the memory referred to by the address it is given, the value has to come from a dynamic allocation, not an array,
• After fixing that, since g() wants to be able to signal the change to the caller, you need to pass a pointer to what needs to be changed. So, the prototype of g() becomes: int g(int **a);.

Hopefully the above will help you get started. If you tell us more about your algorithm, in particular, what you mean by: "changing" and "writing", you will get better responses.

Edit: to answer your question in the comment:

So when I passed an array to a function it decays to a pointer and this pointer is passed by value. If that pointer is pointing a place I allocated before that call...

If you allocated something before the call, it never was an array to begin with. It can be indexed as an array, but that's not the point. So, maybe you are getting confused by the terminology here?

...when my new function changes the pointed value then that value is changed at caller, too.

The pointed-to value is changed, yes.

I dont want it to be like this, so I need a copy of the pointed value in the new function so that my original pointer's pointed value would not change. am I clear now?

It's clearer now, but then that raises more questions:

• If you are going to dynamically allocate or resize the data in each call to the function, how are you going to return those new pointers? You can't. And that means you have got yourself a memory leak. Unless you free() the data in the (recursively called) function itself.
• How would you resize the pointer? You may not be able to know the size of the data pointed to, unless you use a sentinel value.

Are you using the function to iteratively solve a puzzle or a problem? Are you free()ing your data in each invocation of the function? If you can tell us, exactly what are you trying to do?

All arrays are not pointers.

See these:

http://c-faq.com/aryptr/practdiff.html

http://c-faq.com/aryptr/aryptrequiv.html

http://c-faq.com/aryptr/ptrkindofary.html - specifically this one

Assuming you want the order of the output to be the same as in your original, if you don't want the outer call to see changes to your arrays made in the recursive call, you need to copy them. The easiest way is probably to allocate them on the stack then memcopy from the argument, though that will cause a SO if it gets too big. The second easiest is to malloc and free them. You will probably need to pass the array size around too. You can't pass arrays by value on the stack in C.

Just print them before passing them to the next level of recursion.

Your question isn't terribly clear but what I'm reading is this:

You have a recursive algorithm that operates on two heap-allocated arrays. It is possible that one of the recursive calls will have to reallocate the arrays, and so when it returns to the next level up, the old pointers won't be valid anymore. You want to know how to "pass the arrays by value" in order to avoid this.

First, you cannot pass an array by value in C. Period. Arrays are always passed as pointers to the first element, and there's no way around that.

Second, the answer is always another level of indirection. :)

In order to solve the problem of having to reallocate the arrays during the recursive call, what you want to do is have the function take two pointer-to-pointers (int**), where *a gives the address of the pointer to the first element of the A array, and (*a)[n] gives the nth element of the a array. That way, you can reallocate the array to your heart's content, (changing the value of *a) but the value of a itself always remains the same. By doing this, instances of the function further up the call stack will automatically inherit the reallocations made by the recursive calls because the pointed-to value (*a) of the pointer (a) that they passed to the recursive call was modified to reflect the new location of the actual data.

e.g.

int f(int** a, int** b)
{

  /* Do stuff on arrays using (*a)[n] and (*b)[n] */

  if (some_condition) {
     /* Time to reallocate */
     *a = realloc(*a, new_size);
     *b = realloc(*b, new_size);
  }

  /* Do stuff on arrays using (*a)[n] and (*b)[n] */

  f(a, b);  /* Recursive call */

  /* Do more stuff using (*a)[n] and (*b)[n] */
  /* a and b are still valid pointers, even though *a and *b might point somewhere new */

 return foo;
}

void use_f(void)
{
   int* a = malloc(starting_size);
   int* b = malloc(starting_size);

   f(&a, &b);
}

Given the requirements:

int f(int[] a, int[] b){
----changing a here
----changing b here
f(a,b)
----writing a here
----writing b here
}

What should I do to pass that array to recursive calls as regular "pass by value"?

PS: Arrays may be dynamically allocated or resized etc anywhere in recursive calls.

The code in f() is either authorized to make changes to the arrays (as now), or it is not authorized to make changes. If it is authorized to make changes, then there is nothing much you need to do, except worry about whether you are going to leak memory if you are using dynamic allocation.

If the code is not authorized to change the arrays, then it will have to make copies of the arrays. You can prevent the code from casually modifying them by including appropriate const qualifiers:

int f(const int *a, const int *b) { ... }

Note that you cannot pass arrays by value in C. You could have the caller pass a modifiable copy - or you can have the receiver (callee?) make the copy; one or the other will have to o so if the receiver is going to make modifications when it shouldn't.

The easiest and safest option is to pass a pointer and a size. Say you are working on something like quick-sort:

void sort_range( int* ptr, size_t count )
{
    size_t pivot;

    assert( ptr ); /* make sure we have memory */

    if ( count < 2 ) return; /* terminate recursion */

    pivot = partition( count ); /* select a pivot */

    assert( pivot < count ); /* make sure we don't overrun the buffer */

    sort_range( ptr, pivot ); /* sort left part */
    sort_range( ptr + pivot, count - pivot ); /* sort right part */

    merge( ptr, count, pivot ); /* merge ranges */
}

Always be conscious about size of the memory chunk you are working with. Unfortunately C doesn't make it easy, so you have to develop a habit of checking your memory ranges.