C - recursive function that accepts pointers as parameters problem

Question

I've been given a problem in which I have to write a function that accepts two parameters (both are pointers, the first one points at the beginning of an array and the second one points to the place in memory after the last element of the array)

The function has to be called from the first element of the array to the one in the middle, and then from the middle element to the one at the end, and then the function should return the value of those two which is bigger.

double max_element(double *p1, double *p2)
{
    double from_first_to_middle = max_element(p1, (p1 + p2) / 2 + p1);

    double from_middle_to_last = max_element((p1 + p2) / 2 + p1, p2);

    if(from_first_to_middle > from_middle_to_last)
    {
        return from_first_to_middle;
    }
    else
    {
        return from_middle_to_last;
    }
}

But when I try to run this code it gives me the error

error: invalid operands to binary + (have ‘double *’ and ‘double *’)

So then I thought that I should dereference these pointers as I cannot do these operations with the addresses they point to, but it still does not work.

Can anyone help?

Thanks!

The only valid arithmetic operation on pointers is subtraction, as it might give an offset. Any other operation is meaningless (and is not allowed - see port70.net/~nsz/c/c11/n1570.html#6.5.6p2). You can do something like p1+(p2-p1)/2 instead, as here the second operand for addition will have an integer type (ptrdiff_t). — Eugene Sh.
– Eugene Sh., Commented Dec 21, 2018 at 15:41
Can you please reformulate your specification and question please? It is unclear what you mean by "The function has to be called from the first element of the array to the one in the middle, and then from the middle element to the one at the end, and then the function should return the value of those two which bigger. ". Also, the second pointer points to something after the last element in the array? That sounds dangerous to me. — John
– John, Commented Dec 21, 2018 at 15:44
@John: you usually have to use this convention to simplify aritmetics i.e. p1 == p2 means empty, p1 + 1 == p2 means single item, so p2 - p1 yields 1 although p2 is pointing outside the array. Unless you dereference it, it isn't UB. — vgru
– vgru, Commented Dec 21, 2018 at 15:47
@Groo Sure, if it isn't dereferenced, it's all good. But how can you be sure p2 is after the last element in the array? I won't go any further into this. The question needs refactoring. — John
– John, Commented Dec 21, 2018 at 15:50
Not sure why this question is downvoted. Looks a good one to me. the code needs a bit of formatting though. — Eugene Sh.
– Eugene Sh., Commented Dec 21, 2018 at 15:53

John Bollinger · Accepted Answer · 2018-12-21 15:47:23Z

3

Pointers are not integers. There are only a few arithmetic operations defined for them, and pointer + pointer addition and pointer / integer division are not among them (what would they mean?). You may add an integer to a pointer to get another pointer, offset from the original by the specified number of target objects. Conversely, you can subtract one pointer from another to obtain an integer representing the number of target objects between the two pointed to. There are restrictions on both of these operations, but those should not interfere with what you need to do.

You can use the above kinds of pointer arithmetic operations together with some integer(-only) arithmetic to compute midpoint pointer needed for your function. Details are left as an exercise.

answered Dec 21, 2018 at 15:47

John Bollinger

191k11 gold badges103 silver badges206 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

John · Accepted Answer · 2018-12-21 16:36:45Z

0

Maybe this will help.

double max_element(double *p1, double *p2)
{
    double from_first_to_middle = max_element(p1, (double *)((size_t)(p2 - p1) / 2) + p1);

    double from_middle_to_last = max_element((double *)((size_t)(p2 - p1) / 2 + 1) + p1, p2);

    if (from_first_to_middle > from_middle_to_last)
    {
        return from_first_to_middle;
    }
    else
    {
        return from_middle_to_last;
    }
 }

edited Dec 21, 2018 at 16:36

answered Dec 21, 2018 at 16:19

John

1,02415 silver badges23 bronze badges

7 Comments

Eugene Sh. Over a year ago

max_element is expecting p\ointers. Why would you pass it size_t?

John Over a year ago

@EugeneSh. My bad, fixed.

Eugene Sh. Over a year ago

Still, casting ptrdiff_t into size_t doesn't look like a good idea. Why do you need this cast at all? I would imagine you can get rid of all of the casts.

Eugene Sh. Over a year ago

BTW, looks like the logic is broken. You pass the difference instead of a pointer.

John Over a year ago

@EugeneSh. size_t can safely represent pointer types. Also, we have a precondition that p2 is greater than p1. See viva64.com/en/a/0050 section on Safety of ptrdiff_t and size_t types in address arithmetic

|

roschach · Accepted Answer · 2018-12-22 06:28:27Z

0

I think your code is not to be end, because your return have some problem. if p1 + 1 == p2,then the recursion keep recursing. You should add a line

if ((p1+1) == p2)
 return *p1;

in the beginning.

double max_element(double* p1， double* p2)｛
    if ((p2 - p1) <= 0)
        exit(1);
    if ((p1+1)==p2)
        return *p1;
｝

edited Dec 22, 2018 at 6:28

roschach

9,63617 gold badges92 silver badges141 bronze badges

answered Dec 21, 2018 at 16:32

freeskylover

11 bronze badge

Comments

cdlane · Accepted Answer · 2018-12-23 05:03:52Z

If, instead of using p1 and p2, you were to use pointer names that match your from_first_to_middle and from_middle_to_last variable names, things might become clearer:

double max_element(double *first, double *last)
{
    if (last - first == 1)
    {
        return *first; // base case of our recursion
    }

    double *middle = first + (last - first) / 2;

    double from_first_to_middle = max_element(first, middle);

    double from_middle_to_last = max_element(middle, last);

    if (from_first_to_middle > from_middle_to_last)
    {
        return from_first_to_middle;
    }

    return from_middle_to_last;
}

Although with regular numbers, (p1 + p2) / 2 is the same as p1 + (p2 - p1) / 2, that logic doesn't hold with pointers due to lack of pointer addition. Even then, your formula: (p1 + p2) / 2 + p1 is also wrong for regular numbers.

Collectives™ on Stack Overflow

C - recursive function that accepts pointers as parameters problem

4 Answers 4

Comments

7 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related