title: C - recursive function loses tracks of array's address?
body: <p>I am implementing a binary search. I seem to have solved my problem but I'd like to understand what was going on.</p>
  <p>Here is what I was originally doing for my search:</p>
  <pre><code>void find_index(double *list, int val, int low, int high, int *target)
  {
  
    int mid;
    
    if (list[low] == val)
    {
      target[0] = low;
      return;
    } 
  
    if (list[high] == val)
    {
      target[0] = high;
      return;
    }
    
    mid = (int)((double)(low + high) / 2.0);
    if (list[mid] == val || mid == low || mid == high)
    { 
      target[0] = mid;
      return;
    }
  
    if (list[low] &lt; val &amp;&amp; val &lt; list[mid])
    {
      high = mid;
      find_index(list, val, low, high, target);
    }
  
    if (list[mid] &lt; val &amp;&amp; val &lt; list[high])
    {
      low = mid;
      find_index(list, val, low, high, target);
    }
  
  
    return;
  
  }
  </code></pre>
  <p>In the code above, list is a sorted array of doubles. I allocated it dynamically in the main,</p>
  <p><code> double *list = malloc((N+1)*sizeof(double));</code></p>
  <p>and <code>val</code> is the value to be searched (guaranteed to be in <code>list</code>). The main calls <code>func1</code>, which calls <code>find_index</code>. Here's the story:</p>
  <ol>
  <li>Initially I allocated statically a size1 array, <code>int target[1]</code> into <code>func1</code> and
  passed it to <code>find_index</code>. I got a segmentation fault. Tracking the origin of the error with valgrind I found that, in <code>func1</code>, I was using an uninitialized value  AND THAT THE UNINITIALIZED VALUE WAS CREATED IN <code>func1</code>. <code>target</code> is the only array I allocate in such function so it had to be it.</li>
  <li>I changed the declaration of <code>find_index</code>. Specifically, <code>int *target</code> became
  <code>int target[1]</code> as I seem to understand from <a href="https://stackoverflow.com/questions/3911400/how-to-pass-2d-array-matrix-in-a-function-in-c">this question</a> that this is the proper way of passing statically allocated arrays (despite it deals with 2D arrays). I got segmentation fault again and the same message from valgrind.</li>
  <li>I declared <code>target</code> dynamically in the main  <code> int *target = malloc(1*sizeof(int));</code>, passed it to <code>func1</code> and then to <code>find_index</code>. The way I passed it to both functions is the same as how I was originally doing, i.e., both functions takes as argument a <code>int *target</code>. It worked, no complain from valgrind.</li>
  </ol>
  <p>However I am suspicious now so I decided to change the type of <code>find_index</code> to <code>int</code> and declared <code>target</code> as a scalar into <code>find_index</code> itself. To my understanding of recursions, it should be safe.</p>
  <p>However, I do not understand what was going on during steps 1-3 and I'd like to, so to prevent future mistakes. My only guess is that, during the numerous recursive calls that <code>find_index</code> implements, it loses track of the address of the array I originally allocated. Is this something that can happen? Under what circumstances? Could it be related to how I pass the array to the functions and/or to where I originally declared?</p>
  <p>I have searched but could not find a truly related question.</p>
  <p><strong>EDIT: minimal reproducible example shows the situation is more involved</strong></p>
  <p>The minimal reproducible example I could build follows:</p>
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;unistd.h&gt;
  #include &lt;math.h&gt;
  #include &lt;time.h&gt;
  
  void func1(double **list, double **another_list, int N);
  void func2(double **list, double **another_list, int N);
  void find_index(double *list, int val, int low, int high, int *target);
  void q_sort_with_doublelst(double *ary,double *lst,int low,int high);
  int q_partition_with_doublelst(double *ary,double *lst,int low,int high);
  void swap_with_doublelst(double *ary,double *lst,int i,int j);
  
  ////////////////////////////////////////////////////////////////////////
  
  // quick sort 
  
  void q_sort_with_doublelst(double *ary,double *lst,int low,int high)
  {
      int pivotloc;
  
      if(low&lt;high)
      {
          pivotloc=q_partition_with_doublelst(ary,lst,low,high);
          q_sort_with_doublelst(ary,lst,low,pivotloc-1);
          q_sort_with_doublelst(ary,lst,pivotloc+1,high);
      }
  }
  
  int q_partition_with_doublelst(double *ary,double *lst,int low,int high)
  {
      int i,pivotloc;
      int pivotkey;
  
      swap_with_doublelst(ary,lst,low,(low+high)/2);
      pivotkey=ary[low];
      pivotloc=low;
  
      for(i=low+1;i&lt;=high;i++)
      {
          if(ary[i]&lt;pivotkey) swap_with_doublelst(ary,lst,++pivotloc,i);
      }
      swap_with_doublelst(ary,lst,low,pivotloc);
      return pivotloc;
  }
  
  void swap_with_doublelst(double *ary,double *lst,int i,int j)
  {
      int tmp_ary;
      double tmp_lst;
  
      tmp_ary=ary[i]; tmp_lst=lst[i];
      ary[i]=ary[j]; lst[i]=lst[j];
      ary[j]=tmp_ary; lst[j]=tmp_lst;
  }
  
  
  ////////////////////////////////////////////////////////////////////////
  
  
  void func2(double **list, double **another_list, int N)
  {
  
    int i, j;
    double x;
  
    for(i=0; i&lt;=N; i++)
    {
      j = (int) lrand48()%(N+1);
      x = lrand48();
      list[0][i] = j;
      list[1][i] = x;
  
      j = (int) lrand48()%(N+1);
      x = lrand48();
      another_list[0][i] = j;
      another_list[1][i] = x;
  
    }
  
  
  
  
  }
  
  void func1(double **list, double **another_list, int N)
  {
  
    int i, j;
    int binary_index[1];
  
    double x, y;
  
    for(i=0; i&lt;=N; i++)
    {
  
      find_index(list[0], i, 0, N, binary_index); 
  
      j = binary_index[0];
  
      x = another_list[0][j];
      y = another_list[1][j];
  
    }
    return;
  }
  
  
  
  
  
  void find_index(double *list, int val, int low, int high, int *target)
  {
  
    int mid;
    
    if (list[low] == val)
    {
      target[0] = low;
      return;
    } 
  
    if (list[high] == val)
    {
      target[0] = high;
      return;
    }
    
    mid = (int)((double)(low + high) / 2.0);
    if (list[mid] == val || mid == low || mid == high)
    { 
      target[0] = mid;
      return;
    }
  
    if (list[low] &lt; val &amp;&amp; val &lt; list[mid])
    {
      high = mid;
      find_index(list, val, low, high, target);
    }
  
    if (list[mid] &lt; val &amp;&amp; val &lt; list[high])
    {
      low = mid;
      find_index(list, val, low, high, target);
    }
  
    return;
  
  }
  
  
  int main (int argc, char **argv)
  {
  
    int i, N;
    int seed=time(0);
    srand48(seed);
  
    N = 1000000;
  
  
    double **list = (double **)malloc(2*sizeof(double *)); 
    list[0] = (double *)malloc((N+1)*sizeof(double));                       // contains only ints
    list[1] = (double *)malloc((N+1)*sizeof(double));                       // contains double
  
    double **another_list = (double **)malloc(2*sizeof(double *)); 
    another_list[0] = (double *)malloc((N+1)*sizeof(double));               // contains only ints
    another_list[1] = (double *)malloc((N+1)*sizeof(double));               // contains double
  
    for(i=0; i&lt;=N; i++) list[0][i] = i;
  
    while(1 &lt; 2)
    {
      func2(list, another_list, N);
      q_sort_with_doublelst(list[0], list[1], 0, N);
      func1(list, another_list, N);
    }
  
    free(list[0]);
    free(list[1]);
    free(list);
  
    free(another_list[0]);
    free(another_list[1]);
    free(another_list);
  
    return 0;
  
  }
  
  </code></pre>
  <p>I tried to reproduce the error by deterministically filling <code>list[0]</code> with the for loop in the main (line 173), so to have it already sorted. It turns out it does not crash. The code I am posting is more similar to my true code, but now I am afraid (as comments suggest) that I have a problem with recursions. A summary of what the minimal example does (very similarly to my code):</p>
  <ol>
  <li>Fill <code>list[0]</code> with random integers in [0, N]. Fill list<a href="https://stackoverflow.com/questions/3911400/how-to-pass-2d-array-matrix-in-a-function-in-c">1</a> with random double.</li>
  <li>Fill <code>another_list</code> in the same way.</li>
  <li>Sort <code>list[0]</code> by preserving the relation with <code>list[1]</code>.</li>
  <li>Binary-search <code>list[0]</code> and use the index found to take values from <code>list[1]</code> and <code>another_list</code>.</li>
  </ol>
  <p><strong>There is a difference between this example and my true code</strong>: here <code>list[0]</code> is not guaranteed to contain the value I am searching. Further, here <code>list[0]</code> may contain duplicates. In principle the search is written with the idea that the value searched needs not to be present and the idea that there are no duplicates. Thus, I would say that if the value is not present, the search should give me the closest value found, but I have no clue to what happens if there are duplicates. I guess it should give me the index of one the possible duplicates, but I am definitely unsure. In my original code there are no duplicates.</p>
  <p>I am afraid the present code crashes because of the presence of duplicates. Still, it would be great if someone can identify a different problem. Let me stress that valgrind gives me the same exact message: the error should with <code>target</code>, as it is the only array allocated in <code>func1</code>.</p>