Recursion in an array

[sdsu619]

Hey I am trying to use recursion to write this function

 // Return the subscript of the first negative element in the array.
	  // If no element is negative, return -1.
	int firstNegative(const double a[], int n)
	{
	     if (n < 1) 
			return -1;
             if (a[0] < 0) 
			return 0;
        return 1 + firstNegative(a+1, n-1);

	}

And it works fine,as long as there is a negative. However, if there is no negative in the array, such as {1,2,3}, in this case it will return 2 instead of -1. Anyone have an idea of how to solve this?
Im not allowed to use any for, while, loops etc.

[JLBorges]

This is one way (which is tail-recursive):

// Return the subscript of the first negative element in the array.
// If no element is negative, return -1.
int first_negative( const double a[], int n, int start_pos = 0 )
{
    if( start_pos == n ) return -1 ;
    if( a[start_pos] < 0 ) return start_pos ;
    return first_negative( a, n, start_pos+1 ) ;
}

[sdsu619]

Hey thanks for the reply. Unfortunately i failed to mention that im also not allowed to change the parameters.

[JLBorges]

Not tail-recursive:

// Return the subscript of the first negative element in the array.
// If no element is negative, return -1.
int first_negative( const double a[], int n )
{
    if( n == 0 ) return -1 ;
    if( a[0] < 0 ) return 0 ;
    int r = first_negative( a+1, n-1 ) ;
    return r + ( r != -1 ) ;
}

[tntxtnt]

here's my explanation for JLBorges code:

from your function

int firstNegative(const double a[], int n)
{
  if (n < 1)  return -1;
  if (a[0] < 0)  return 0;
  return 1 + firstNegative(a+1, n-1);
}

the only problem is when there is no negative in the array, or firstNegative(a+1, n-1) return -1, so let's add an exception for that:

int firstNegative(const double a[], int n)
{
  if (n < 1)  return -1;
  if (a[0] < 0)  return 0;
  if (firstNegative(a+1, n-1) == -1) return -1; //special case
  return 1 + firstNegative(a+1, n-1);  //next != -1
}

or

int firstNegative(const double a[], int n)
{
  if (n < 1)  return -1;
  if (a[0] < 0)  return 0;
  int next = firstNegative(a+1, n-1);
  if (next == -1) return -1; //special case
  return 1 + next;
}

You can stop here, or think further to shorten your code as JLBorges did:

in the special case, because next==-1 so instead of return -1 we can return next, or 0 + next

  if (next == -1) return 0 + next; //special case
  return 1 + next;

as you can see, the function returns [0 or 1] + next, depends on next==-1(0) or next!=-1(1), so we can simply use (next!=-1) (which returns false/true or 0/1) to replace [0 or 1]

int firstNegative(const double a[], int n)
{
  if (n < 1)  return -1;
  if (a[0] < 0)  return 0;
  int next = firstNegative(a+1, n-1);
  return (next != -1) + next;
}

[sdsu619]

Ah thanks for the help, just started learning recursive functions and they seem quite difficult... Im now working on

 // Return the subscript of the largest element in the array.  If
	  // more than one element has the same largest value, return the
	  // smallest subscript of such an element.  If the array is empty,
	  // return -1.
	int indexOfMax(const double a[], int n)
	{
	    return 0;
	}

How can i compare one number in the array to the rest though?

[JLBorges]

> How can i compare one number in the array to the rest though?

You do not need to compare one number with all the other numbers in the array, but just with one other number (which is the largest so far).

int index_of_max( const double a[], int low, int high )
{
    if( low == high ) return low ;
    int s = index_of_max( a, low+1, high ) ;
    return a[s] > a[low] ? s : low ;
}

int index_of_max( const double a[], int n )
{ return n==0 ? -1 : index_of_max( a, 0, n-1 ) ; }

[sdsu619]

How can i store the largest number in the array so far without another function? So using only the function header

int indexOfMax(const double a[], int n)
{
}

[JLBorges]

> How can i store the largest number in the array so far without another function?

The function would then need to move the elements of the array in a way that the largest number in the array so far is at a known position. Such a function would be a bad function; it would not be const-correct.

[sdsu619]

Hm in that case I must be missing something. Thanks for your responses though, very helpful.

[vlad from moscow]

My five cents.

#include <functional>
#include <iostream>

namespace
{

template <typename InputIterator, typename Size, typename UnaryPredicate>
Size find_if( InputIterator first, Size n, UnaryPredicate unary_predicate )
{
	const Size npos( -1 );

	if ( n == 0 ) return ( npos );
	if ( unary_predicate( *first ) ) return ( Size( 0 ) );

	Size i = find_if( ++first, --n, unary_predicate );

	return ( ( i == npos ) ? npos : ++i );
}

}

int main()
{
	int a[] = { 1, 2, 3 };
	int b[] = { 1, 2, -3 };
	int c[] = { 1, -2, 3 };
	int d[] = { -1, 2, 3 };

	std::cout << "a[] - " << find_if( a, 3, std::bind2nd( std::less<int>(), 0 ) ) << std::endl;
	std::cout << "b[] - " << find_if( b, 3, std::bind2nd( std::less<int>(), 0 ) ) << std::endl;
	std::cout << "c[] - " << find_if( c, 3, std::bind2nd( std::less<int>(), 0 ) ) << std::endl;
	std::cout << "d[] - " << find_if( d, 3, std::bind2nd( std::less<int>(), 0 ) ) << std::endl;

	return 0;
}