Why is my recursiveMinimum function not working?

Question

#include <iostream>
using namespace std;

int recursiveMinimum(int [], int n);

int main () 
{
    int theArray[3] = {1,2,3};

    cout << recursiveMinimum(theArray, 0);
    cout << endl;
    return 0;
}


// pass in array and 0 to indicate first element
// returns smallest number in an array
int recursiveMinimum (int anArray[], int n) // nth element is smallest element in anArray
{
    while (anArray[n+1] != NULL)
    {
     int smallest = n;
     if (anArray[n+1] <= anArray[n])
      smallest = n + 1;
     //if last element has not been reached
     return recursiveMinimum(anArray, smallest);
    }
}

My function exits, but it doesn't return anything. I tried to set the base case to when the outside of the array is reached. The return 0 line in main is reached so I'm pretty sure the base case in my function is being reached.

Here is the working function:

#include <iostream>
using namespace std;

 int recursiveMinimum(int a[],int min,int index,int size);

int main()
{
    int a[6] = {8, 2, 55, 3, 11, 9};
    cout << recursiveMinimum(a,a[0],1,6) << endl;
    return 0;
}

// pass in the array, the first element, 
// 1 to indicate 2nd element, and the number of elements
int recursiveMinimum(int a[],int min,int i,int size)
{
    if(i == size )
       return min;

    else if(i < size)
    {
       if(a[i] < min)    
          recursiveMinimum(a,a[i], i + 1, size);
       else 
          recursiveMinimum(a,min, i + 1, size);      
    }

}

Thank you to everyone who helped. Due to time constraints I sent out a SOS (Stack Overflow distress Signal), however next time I will definitely step through the debugger prior to asking a question.

Answer 1

You need to have an end case with a recursive function.

At the moment, your function always returns itself. This will recurse until the stack runs out. You need to have a check that says "I'm done", which will return a value rather than the result of another function call.

Answer 2

Because your while loop never terminates. Why are you sure anArray[n+1] will ever be NULL?

Answer 3

You never break your recursion. Actually I wonder that this compiles as your function doesn't even have a defined return value in case it reaches the end. Also using while there seems unnecessary as the function execution stops after the return anyway.

Answer 4

Have you stepped through this in a debugger? It should become fairly obvious when you do.

Answer 5

You are recursing within the while loop:

while( condition ) recursive call while( condition ) recursive call . . .

Instead what you probably were thinking was

if( condition ) recursive call recursive call recursive call

you see? Get rid of the while and replace it with an "if" statement.

Answer 6

Instead of

int recursiveMinimum(int array[], int n);

I think that recursiveMinimum should be defined as

int recursiveMinimum(int array[], int index, int length);

with the intention that recursiveMinimum will return the minimum value in array between indexes index and length (i.e., min array[i] where i in [index, length)). Of course, you want to define this recursively. So then I would note that the minimum value in array between indexes index and length is

min(array[index], recursiveMinimum(array, index + 1, length));

Of course, there are boundary cases (such as when index = length - 1). In this case you would just return array[index] as the minimum.

Hope this helps. Let me know if this does not make sense.

Answer 7

 int recursiveMinimum(int a[],int min,int index,int size)
{
    if(index == size )
       return min;

    else if(i < size)
    {
       if(a[i] < min)    
          recursiveMinimum(a,a[i],++index,size);
       else 
          recursiveMinimum(a,min,++index,size);      
    }

}

int main()
{
    int a[] = {1,2,3,0,-4};
    int min = recursiveMinimum(a,a[0],1,5));
    return 0;
}

When you use recursion make sure that you must put some exit condition to end it ,otherwise you will have in infinite recursion and you program will hang.

I think finding minimum is more efficient,easy and simple using iteration rather than recursion.

Answer 8

You're misunderstanding the point of a recursive function. If a certain condition is true, then you return the result of a call to the recursive function, otherwise you return some other value. For example, here is a recursive definition of the factorial function (e.g. 5!, or "5 factorial", is 5*4*3*2*1, which is 125):

int
factorial (int n)
{
  if (n == 1)
    return n;
  return (n * factorial (n - 1));
}

How it works:

• If n is 1, then return 1 since 1! is 1.

• Otherwise, return n multiplied by one less than n.

For example, if n is 5, then the return value is the result of the expression 5 * factorial (5 - 1), which is the same as 5 * factorial (4). Of course, the same thing happens again since it's a recursive function and 4 is not 1. So you end up with 5 * factorial (4), which is the same as 5 * (4 * factorial (4 - 1)), or 5 * (4 * factorial (3)).

You should be able to see the pattern now and how the factorial function works. Your recursiveMinimum function should adhere to the same general idea -- if something is true (or not true), return the result of a call the function (possibly with some additional things like the value n inside the factorial function needs to be multiplied by the result of the factorial function), else return a certain value and code the function to handle it appropriately. In other words, you need a "final" exit condition, such as the n == 1 condition in the factorial function above.

Good luck!