recursion

[irmako]

Hi everyone, I need your help please;
I have a function which finds the index of maximum of vector! I need to change it into recursion function

template<typename T>
int maximal(const vector<T> &x)
{
    int offset(0);
    for(int i=1; i<x.size(); i++)
        if( x[offset] < x[i] )
            offset = i;
    return offset;
} 

if you can help me I will be glad

[vlad from moscow]

Well, I see that nobody has suggested any code till now.

There is nothing difficult to write such a recursive function

template <typename T>
typename std::vector<T>::size_type max_element( const std::vector<T> &v )
{
	if ( v.size() < 2 ) return ( 0 );

	typename std::vector<T>::size_type pos = max_element( std::vector<T>( v.begin() + 1, v.end() ) );
	return ( ( v[++pos] < v[0] ) ? 0 : pos );
}

I hope you are glad.:)

[Kazekan]

Go ahead and take a look at this site first and read what they have to say about Recursive Functions. There's even a section on turning a for loop into a recursive function that should help out quite a bit.

http://www.cs.umd.edu/class/fall2002/cmsc214/Tutorial/recursion2.html

If it's still not clear, write back with the specific issues you're running in to, as well as what code you've been able to come up with on your own.

Happy coding!

[ne555]

O(lg n), xP.

random_iter max_element( random_iter begin, random_iter end){
  if(next(begin) == end) return begin;
  left = max_element( begin, begin+distance(begin, end)/2)) );
  right = max_element( begin+distance(begin, end)/2), end) );
  return (*left<*right)? right: left;
}
size_t max_element( const vector &v){
  //if(v.empty()) return 42;
  return distance( begin, max_element(v.begin(), v.end()) );
}

[vlad from moscow]

@ne555,

It will be correct to write

if( begin == end ) return begin;

instead of

if(next(begin) == end) return begin;

[ne555]

Nope, when you return from the recursion you'll try to dereference an invalid iterator.
Well, you could fix it by making [] the first call

size_t max_element( const vector &v){
  //if(v.empty()) return 42;
  return distance( begin, max_element(v.begin(), v.end()-1) );
}

[irmako]

thanks a lot, your advices are very helpful for me

[vlad from moscow]

@ne555,
But otherwise you were trying to advance the iterator after the last.:)

This statement

return distance( begin, max_element(v.begin(), v.end()-1) );
is also invalid in case of empty vector.


Also I would like to note that you are wrong saying that the algorithm has difficulty of O( lg N ). In all casses it has the difficulty of O( N ).

[ne555]

The empty vector case is invalid.
There is no maximum or minimum defined. Threat it in the wrapper as you please.
I don't see how I'm going over the last iterator.

O(lg n) in the recursion depth. If you've got O(n) processors you could make it in O(lg n) in time.

[vlad from moscow]

@ne555.

Your code contains a bug. let consider a vector of two elements { 0, 1 }
You pass v.begin() and v.end() - 1. *v.begin() == 0 and *( v.end() - 1 ) == 1.
Then you check

if(next(begin) == end) return begin;


and indeed next( v.begin() ) == v.end() - 1

So you return begin. But the maximum is end() - 1.

I think it can be corrected the following way

return ( std::distance( v.begin(), max_element1( v.begin(), v.end() ) ) );

and in the second function

if ( begin == end || std::next( begin ) == end ) return ( begin );

[ne555]

You misunderstood me.
This call return distance( begin, max_element(v.begin(), v.end()-1) ); is when you've got begin==end

return distance( begin, max_element(v.begin(), v.end()) ); works perfectly fine with next(begin) == end
but it will not with begin==end as you will dereference an invalid iterator ( v.end() )

The empty case should be handled in the wrapper, so there is no chance for begin==end to be true.

[vlad from moscow]

I would change simply the condition

if ( begin == end ) return ( begin );

to

if ( begin == end || std::next( begin ) == end ) return ( begin );

This corresponds more to the semantic of std::min_element. Only the check

if ( std::min_element( v.begin(), v.end() ) == v.end() )

would be changed to

if ( min_element( v ) == v.size() )

[ne555]

I just hate that extra check, that it is not needed as it is handled before all the recursive part.

min_element( v ) == v.size() you can still have that. *wrapper*

[vlad from moscow]

I agree but it is the compromise with the similarity with std::min_element and all other standard algorithms.

Though it will be enough to insert the check inside the first min_element

size_t max_element( const vector &v){

  return ( v.begin() == v.end() ) ? 0
                                                : distance( begin, max_element(v.begin(), v.end()-1) );
}