Getting segmentation fault while using call by reference to return multiple values in recursive function

Question

The question is to find the maximum and minimum element in an array and return their difference. I referred to the editorial of the problem on GeeksforGeeks. I used the tournament method, in which we partition any array having more than two elements into 2 parts, and find the maximum and minimum of those two arrays, and then return the answer after comparing these final values. The official solution listed here , uses a struct pair. I wanted to do it using call by reference values.

Initially I tried to return 2 values with the function like:

int r1,r2= Sample(a,high,low)

That is wrong(as we can return only 1 value from the function) So I tried passing by reference like this:

void halfarrsol(int arr[], int low, int high, int &mi, int &ma){
int mid, min,max;
if(low==high){
    mi=ma=arr[low];
}
if(high==low+1){
    mi=arr[low], ma=arr[high];
    if(arr[low]>arr[high]){
        mi=arr[high];
        ma=arr[low];
    }
}
else {
    mid=(low+high)/2;
    halfarrsol(arr, low,mid,mi,ma);
    int minl=mi, maxl=ma;
    halfarrsol(arr, mid+1,high,mi,ma);
    int minr=mi, maxr=ma, fin=minl;
    if(minl>minr){
        fin= minr;
    }
    int fax=maxl;
    if(maxl<maxr){
        fax=maxr;
    }
    mi= fin;
    ma=fax;
}
}

The idea is that when I call the function, the final value of min and max (mi and ma) will be available. One obvious error that I think might be messing things up is the

halfarrsol(arr, low,mid,mi,ma);
      int minl=mi, maxl=ma;

What I'm trying to here is store the obtained mi and ma vales(for this half array) in 'minl' and 'maxl' variables. Is this valid? The overall code gives a segmentation error, and timeout: the monitored command dumped core error. I'm not sure what exactly I'm messing up, or if this approach is completely wrong. I wanted to be able to solve this question without using a Struct Pair, and without using another class and creating an object. There are also solutions like using a Tuple to store min and max values, but I considered them to be more applicable for when we have many return values, as here I am using 2 values only. Is there any way to solve this problem recursively using call by reference?
If required you can view the driver code here

you should declare variables only when you can initialize them. `mid` requires to scan the whole function to check that it is initialized properly and `max` and `min` are not used at all. — 463035818_is_not_an_ai, Jun 12 '23 at 11:34
Using recursion for this seems wrong. If your array has millions of elements, that recursion will go very deep. — Ted Lyngmo, Jun 12 '23 at 11:35
and try to use descriptive names. Rather than removing single letters to get a different name, add more to make it clear what the variable is for. — 463035818_is_not_an_ai, Jun 12 '23 at 11:35
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Jun 12 '23 at 11:37
Are you sure your references are the problem? With "C" style arrays it is notoriously easy to access them out of bounds (I really wonder why they are still being used/taught). And that might well be the case here too, best option is to start debugging. Or use std::array/std::vector (std::span) and use the .get operations on them instead of the index operators []. get will do some extra checks for you — Pepijn Kramer, Jun 12 '23 at 11:37
And when you used your debugger to debug your crash, what did you see, exactly that led you to conclude that the crash was caused by passing those parameters by reference? What led you to conclude that this must be the problem? — Sam Varshavchik, Jun 12 '23 at 11:39
Fwiw, the "official" solution you link to is poor code. It uses many poor practices. `using namespace std;`, using `sizeof` to get the size of an array, define a custom `Pair` rather than using `std::pair`. Its actually better than most other code found on this site, but still enough to warn you. — 463035818_is_not_an_ai, Jun 12 '23 at 11:41
Perhaps `if(high==low+1){` should have been `else if(high==low+1){` ? The lack of `else` there looks wrong. — chi, Jun 12 '23 at 11:46
It's quite possible that your "official" solution is wrong; geeksforgeeks is largely rubbish and not worth what you're paying for it. — molbdnilo, Jun 12 '23 at 11:46
@463035818_is_not_a_number Yes, my bad. `mid` should be initialized in the else loop, and `min` and `max` were unnecessary. Thanks for pointing that out! Will also use more descriptive names in the future, I apologise for the poorly written names. — user22021739, Jun 12 '23 at 14:56
@TedLyngmo Oh, I see. If you don't mind, what kind of solution would be optimal? — user22021739, Jun 12 '23 at 14:58
@molbdnilo Thanks for this info, as it's trusted very widely where I'm from (I missed all the signs that @ 463035818_is_not_a_number pointed out). Will be grateful if you have a better alternative. — user22021739, Jun 12 '23 at 15:08
@user22021739 _"what kind of solution would be optimal"_ - I suspect that using [`std::minmax_element`](https://en.cppreference.com/w/cpp/algorithm/minmax_element) would be pretty close to optimal. — Ted Lyngmo, Jun 12 '23 at 15:12

score 0 · Answer 1 · answered Jun 12 '23 at 11:51

The bug is not easy to figure out if you are focused on logic. Your logic is more or less correct, issue is that when low == high, then it will call function recursively for indefinite times since you are not returning neither you have used else if for high == low + 1. Change to following:

...
if(low==high){
    mi=ma=arr[low];
}
else if(high==low+1){
    mi=arr[low], ma=arr[high];
    if(arr[low]>arr[high]){
        mi=arr[high];
        ma=arr[low];
    }
}
else {
...

I'm not clear on what the `else if` helps with... how does it stand in for a return statement? — user22021739, Jun 12 '23 at 15:14

Jean-Baptiste Yunès · Accepted Answer · 2023-06-12T14:41:07.157

Your recursion never stops. You forgot to end it in the very first case:

if(low==high){
    mi=ma=arr[low];
}

It then enters the second if, where the condition is false, and then goes to the else...

At least change to:

if(low==high){
    mi=ma=arr[low];
    return
}

Aside, the min/max can be computed more easily:

mid=(low+high)/2;
halfarrsol(arr, low, mid, mi, ma); // get min/max
int minr, maxr;
halfarrsol(arr, mid+1, high, minr, maxr); // get right min/max
if (mi>minr){ // correct min if needed
    mi = minr;
}
if (ma<maxr){ // correct max if needed
    ma=maxr;
}

Getting segmentation fault while using call by reference to return multiple values in recursive function

2 Answers2