How to make the C++ recursion program terminate

Question

Why the program does not terminate after the return and how to make it terminate ? https://ideone.com/9Lz6jy Note: The intent here is to find median if that helps in understanding the program. But my question is pure C++ related. No help needed in finding median. Please focus on how I can return the answer once I have fount it.

#include <iostream>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h> 

using namespace std;


int Pivot2(vector<int> &v, int pivot) {

    vector<int> v_copy(v.size()); 
    //int pivot = v.size() / 2; 
    //1. Sort the array about the mid term  
    int count_less = 0; 
    int j = 0; 
    for (unsigned int i = 0; i <v.size() ; i++) {

        if (v[i]< v[pivot]) {
            v_copy[j]=v[i]; 
            j++; 
            count_less++; 
        }
    }

    v_copy[j]=v[pivot];
    j++; 

    for (unsigned int i = 0; i <v.size(); i++) {

        if (v[i]> v[pivot]) {
            v_copy[j] = v[i];
            j++; 
        }
    }

    //2.  if the number of less than  than tmp_med increase the middle postion 
    if ( count_less >  v.size() / 2) {
        Pivot2(v_copy,count_less-1);
    }
    else if (count_less ==  v.size() / 2) {
        cout <<"inner " <<  v[pivot] <<endl ; 
        return v[pivot]; //Why the recursion does not terminate with this return?
    }
    else {
        if ( count_less < v.size() / 2) {
            Pivot2(v_copy, count_less + 1 );
        }
    }



}


int main() {
    // your code goes here
    int arr[] = { 8, 7, 3, 1, 9, 4, 6, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]); 
    //randomize(arr, n);
    vector<int> v( begin(arr), end(arr) );

    int med1 = Pivot2(v,v.size()/2);
    assert(5 == med1);
    cout << med1 <<endl ; 
    return 0;
}

Why are you not returning the values on calling `Pivot2()` in `if-else if` conditions? — Atri, Jan 15 '16 at 23:13
You should turn on warnings in your compiler. If you use g++, use -Wall. That will tell you that you are not returning a value from all paths of your Pivot2 function. I see 3 places where you are missing a return. — AaronI, Jan 15 '16 at 23:15
Possible duplicate of [Recursive function does not return specified value](http://stackoverflow.com/questions/27691547/recursive-function-does-not-return-specified-value) — Barmar, Jan 15 '16 at 23:33

hlscalon · Answer 1 · 2016-01-15T23:22:49.633

First of all, enable compilers warnings as you are doing several comparisons between signed and unsigned integer expressions. ie : if ( count_less > v.size() / 2) {

Then you need to return the Pivots you create

    return Pivot2(v_copy,count_less - 1);
    ^^^^^^^^
    .....
    return Pivot2(v_copy, count_less + 1 );
    ^^^^^^

Also, be careful that your function reaches end of non-void function. Simply remove if ( count_less < v.size() / 2) { and it will be fine. ie:

else {
    return Pivot2(v_copy, count_less + 1 );
}

You can check this version on Coliru

score 0 · Accepted Answer · answered Jan 15 '16 at 23:20

You need to return values in all condition from this block:

if ( count_less >  v.size() / 2) {
    return Pivot2(v_copy,count_less-1);
}
else if (count_less ==  v.size() / 2) {
    cout <<"inner " <<  v[pivot] <<endl ; 
    return v[pivot]; //Why the recursion does not terminate with this return?
}
else {
    if ( count_less < v.size() / 2) {
        return Pivot2(v_copy, count_less + 1 );
    }
}

How to make the C++ recursion program terminate

2 Answers2