1 
#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.

Improve this question
3
  • 1
    If you post what's wrong with it, people will be more likely to help. It may also give a clue how to fix the problem. Commented Dec 18, 2009 at 14:33
  • you should add a 'recursion' tag to this question Commented Dec 18, 2009 at 15:00
  • You've almost certainly read your assignment wrong. The n parameter probably tells you the effective length of the array. If n really is the current best minimum, then you have made the input array incorrectly because it needs to have a sentinel (such as 0) at the end. As your code is now, you have no way to recognize when you've run out of array elements. Check with your instructor to make sure you've understood the requirements correctly, or else you'll be wasting a lot of time pursuing the wrong answer. Commented Dec 18, 2009 at 15:55

8 Answers 8

Reset to default
4

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

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

If he's taking a class like the one I used to help teach, he hasn't learned about debuggers, and he probably doesn't have time to learn how to use one before the assignment is due at the end of the semester, either.
That may be the case if he's using Linux/GCC, but most likely he has Visual Studio installed. What can be harder than setting a break-point and tapping F10/F11? Also, installing Visual C++ Express Edition takes like 5 minutes? In addition to that, I'm sure the OP can get the full blown VS2008 at reduced educational cost from his/her school! If they are really using Linux GCC, it takes like 5 minutes to Google a simple tutorial on the web! There simply are no excuses!
3

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.

Improve this answer

4 Comments

The condition is bad to begin with. n + 1 is not necessarily a valid index into the array. And checking for NULL? What is that accomplishing?
I was trying to check for the outside of the array using NULL.
Brandon, once you have something working mind posting it up here? I bet you could elicit more commentary. Howver, Jason is correct that NULL is not a good condition to check for the end of an array. There's no guarantee NULL will be found! People generally pass along the size of the array in C functions. While you often can do '/0' for strings I don't think the same can be said for an arbitrary array.
Ok no problem. Its going to take me a bit because I am still not sure how to fix it, but when I do I will update for sure. Thanks!
2

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.

Improve this answer

2 Comments

it's simple to get around 'end cases' in recursion by having recursive methods run out of data to work with
Yes, but they have to stop calling themselves!
1

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

Improve this answer

1 Comment

Let me make the point explicitly. Only strings are null-terminated. An array created with curly braces will not have a null character at the end. The way around this is to explicitly put a number at the end to signify the end of the array: {1, 2, 3, -1}, or pass the length of the array as an argument to the recursiveMinimum function.
1

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.

Improve this answer

Comments

1

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.

Improve this answer

Comments

1

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!

Improve this answer

Comments

1 
 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.

Improve this answer

2 Comments

Thanks for taking the time to code this. I modified it a bit and it worked like a charm.
Brandon it took hardly 45 sec just to write it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.