1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[C] Use recursive function to get the min value of an array

  1. Apr 15, 2017 #1
    1. The problem statement, all variables and given/known data
    Using these two prototypes,
    double minValue( const double a[], unsigned els);
    double minIndex(const double a[], unsigned els);
    I am supposed to find the smallest value of an array using the minValue function as well as it's index by using the separate minIndex function and without using any loop. For both arrays, els is the number of elements in the array a being passed to the function and the function may assume that els > 0. I may also use a helper function if it is necessary.

    This is something that I can do quite easily with a loop but, for whatever reason, seem to be having trouble making it work as a recursion.

    2. Relevant equations
    N/A

    3. The attempt at a solution
    I have attached my two attempts at this program as text files but here's the gist of things:

    I first created a version of minValue that is supposed to initialize the double min with the first element of a (min = a[0]), then min was passed to a helper function that would do the rest of the heavy lifting by comparing each of the subsequent values of a to min.
    My first attempt is dotted with lots of code to help me figure out where things were going wrong after my less than stellar attempt to try debugging with gdb. I am using archlinux, btw.
    After getting the obvious bugs out, I am able to compile the program with no trouble except for the fact that I can't seem to get the correct answer. Following the variables in gdb as well as my own printf() checking seems to show that after els reaches the "critical" point where the recursion should stop and the minimum value should be given back to main(), it starts getting larger and then, to top it off, despite having the correct value inside of min while in the scope of the recursion, the wrong value is passed back.

    I took a different approach with the second program thinking that perhaps a static double would be of some use. Unfortunately I am still hitting a wall as far as passing arguments and am really not sure what my next step should be. I think that either method should work but, I am hitting a wall and turning to the forums for help.

    Mod note: Inserted the text of the code into the post
    Code (C):

    //lab170412b.c

    #include <stdio.h>
    #include <stdlib.h>

    double minValue(const double a[], unsigned els);
    double minValueHelper(const double a[]);
    double minIndex(const double a[], unsigned els);

    int main()
    {
     unsigned size = 3;
     double a[] = {1, -1, 2};
     double minimum;
     unsigned index;
     //minimum = minValue(a, size);
     for (unsigned i = 0; i < size; i++)
     {
      printf("a[%i]: %f\n", i, a[i]);
      minimum = minValueHelper(a);
     }
     printf("min: %f\n", minimum);
    }

    double minValue(const double a[], unsigned els)
    {
     minValueHelper(a);

     if (els - 1 == 0)

     minValue(a + 1, els - 1);
    }

    double minValueHelper(const double a[])
    {
     static double min = 0;
     min = a[0];

     if (min > a[0])
     {
      printf("%f is less than %f\n", a[0], min);
      min = a[0];
     }
     return min;
    }

    double minIndex(const double a[], unsigned els)
    {
     return 0;
    }
     
    Code (C):

    //lab170412.c
    #include <stdio.h>
    #include <stdlib.h>

    //AWOC that els > 0, return INDEX OF (first)
    //smallest element
    //NO LOOPING
    unsigned minIndex(const double a[], unsigned els);

    //AWOC (assume w/o checking) that els > 0
    //return the smallest element
    //NO LOOPING
    double minVal(double a[], unsigned els);
    double minValHelper(double a[], unsigned els, double min);

    void show(const double a[], const unsigned els);
    void showValues(const double min, const unsigned els, char fname[]);

    int main()
    {
     char fname[] = "main";
     unsigned size = 3;
     double x, y;
     double a[] = {1, -2, -3, -4, 5, -4, -4};
     double b[] = {-100, 5, 73.2, 99, 100000001, -10000001, 17, -10000001};
     double c[] = {30, -10, 20};

     show(c, size);
     showValues(0, size, fname);
     x = minVal(c, size);
     y = minIndex(c, size);
     printf("Min value a[]: %f\n", x);
     //printf("Min index a[]: %u\n", y);
     //printf("Min value b[]: %f\n", minVal(b, size));
     //printf("Min index b[]: %u\n", minIndex(b, size));

     return 0;
    }


    double minVal(double a[], unsigned els)
    {
     char fname[] = "minVal";
     double min = a[0];
     showValues(min, els, fname);
     //the minimum value in an array is either the first el
     //of the minimum number in the REST of the array
     //whichever is smaller
     min =  minValHelper(a, els, min);
     showValues(min, els, fname);
     return min;
    }

    double minValHelper(double a[], unsigned els, double min)
    {
     char fname[] = "minValHelper";
     showValues(min, els, fname);
     if(els - 1 == 0)
     {
      printf("no change here.\n");
      showValues(min, els, fname);
      return min;
     }
     if (min > a[0])
     {
      min = a[0];
      //showValues(min, els, fname);
     }
     minValHelper(a+1, els-1, min);
     return min;
    }

    unsigned minIndex(const double a[], unsigned els)
    {
     return 0;
    }

    void show(const double a[], const unsigned els)
    {
     printf("[%u]: ", els);

     for (unsigned i = 0; i < els; i++)
     {
      printf("%s%f", i ? ", " : " ", a[i]);
     }
     printf("\n\n");
    }

    //void showValues(const double min, const unsigned els)
    void showValues(const double min, const unsigned els, char fname[])
    {
     static unsigned count = 1;
     printf("count: %u\n", count);
     printf("func: %s\n", fname);
     printf("min: %f\n", min);
     printf("els: %u\n\n", els);
     count++;
    }
     

    Attached Files:

    Last edited by a moderator: Apr 16, 2017
  2. jcsd
  3. Apr 17, 2017 #2

    NascentOxygen

    User Avatar

    Staff: Mentor

    Hi bornofflame. :welcome:

    In your first program, when you call minValueHelper you assign to min the value 0, followed by assigning min the value a[0], then what you're asking is min > min which it never is.

    Where a is an array, just remind me what will happen with the expression a+1
     
  4. Apr 18, 2017 #3
    Thanks for the reply, NascentOxygen.

    Where I have min assigned a value of zero in minValueHelper I was using a static variable so that it would retain the data it's assigned even outside of scope.

    a+1 looks at the next element in the array. a is a pointer to the first element and when you add a number to it, the address is changed to the element in the array that corresponds to the number. So a+0 is the same as just typing a, and *(a+1) is the same as a[1].
     
  5. Apr 18, 2017 #4
    A static variable is not needed at all. What you need to do is to write a function that can compute the minimum of an array of n numbers, using the same function to compute the minimum of an array of n-1 numbers.
    minval(a, els) needs to call minval (als+1, els-1) and then use the result for its own return value.
     
  6. Apr 18, 2017 #5

    NascentOxygen

    User Avatar

    Staff: Mentor

    I showed a flaw in your logic. Please reread.

    But I think you should step back, and return to perfecting a flowchart to do what you need. There is no point writing code until you have a flowchart which you know works,


    As willem2 indicates, you need to devise your entire program to be largely one recursive function that calls itself repeatedly, but include a conditional so it eventually exits, something like:

    function minval (....)
    .......
    IF NOT at the last element then call minval (....) ELSE return
     
  7. Apr 29, 2017 #6
    Thanks for the replies. I was finally able to get it to work sans static variable, helper and all that. Just had some trouble wrapping my brain around recursion more with the manipulating of variables than straight out printing to screen.

    Sorry for the late response. Midterm studying took everything out of me, it felt like. Still have one more late midterm to take. This one for CoSci!
     
    Last edited: Apr 29, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: [C] Use recursive function to get the min value of an array
Loading...