Sign in to follow this  

Find Min with Recursion

This topic is 1447 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I am trying to create an algorithm in C that finds the Min number of an array A[n] using recursion.
 
What the algorithm does is split the array to  2 equal subsections until the subsections become with only one position left. Until n = 1 so min = A[0]. Then it goes back and the subsectopms start comparing each other.
 

 
This is where I have gotten so far.
 

#include <stdio.h>
#define N 10

int min_num(double T[],int n);

int main()
{
	double T[]={4,5,10,5,7,3,6,2,8,9};
	double min;
	min = min_num(T,N);

	printf("min = %g\n",min);
	return 0;
}

int min_num(double T[],int n)
{

	double min; // the min number
	if (n == 1)
		min = T[0];

	else
	{
		int k;
		k = n/2;
		double SubsectionA_T[k];
		double SubsectionB_T[n-k];

		int i;
		double x,y;
		for (i=0;i<k;i++)
			SubsectionA_T[i] = T[i];
		for (i=k; i<N; i++)
			SubsectionB_T[i] = T[i];

		x = min_num(SubsectionA_T, k);
		y = min_num(SubsectionB_T, n-k);
		min = x;
		if (x > y)
			min = y;
	}
	return min;
}

Edited by shadowstep00

Share this post


Link to post
Share on other sites

Yeah true... Too many unnecessary mistakes... I will take a look at the code again. tongue.png

Edited by shadowstep00

Share this post


Link to post
Share on other sites

So I repost the code

#include <stdio.h>
#define N 10

int min_num(double T[],int n);
void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[]);

int main()
{
	double T[]={4,5,10,5,7,3,6,2,8,9};
	double min;
	min = min_num(T,N);

	printf("min = %g\n",min);
	return 0;
}

int min_num(double T[],int n)
{

	double min;
	if (n == 1)
		min = T[0];

	else
	{
		int k;
		k = n/2;


		double SubsectionA_T[k];
		double SubsectionB_T[n-k];

		double x,y;

		subsections( T, n, k,SubsectionA_T, SubsectionB_T);

		x = min_num(SubsectionA_T, k);
		y = min_num(SubsectionB_T, k-n);
		min = x;
		if (x > y)
			min = y;
	}
	return min;
}

void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[])
{
	int i;
	int j = 0;
	for (i=0;i<k;i++)
		SubsectionA_T[i] = T[i];
	for (i=k; i<n; i++)
	{
		SubsectionB_T[j] = T[i];
		j++;
	}
}

The void function has problems with the array index again...(I think)

Edited by shadowstep00

Share this post


Link to post
Share on other sites

You are making it way too complicated. You don't need SubsectionA_T or SubsectionB_T at all. Just call min_num with a pointer into the same array that was passed to the function. Do you know how pointer arithmetic works?

Share this post


Link to post
Share on other sites

Well I think I know. For example if: int *p points to 1004 place in memory. 

The *(p+1) will point on 1008. This is what you mean?

Edited by shadowstep00

Share this post


Link to post
Share on other sites

He wasn't asking for a solution.

 

But here's mine: ;)

#include <stdio.h>

double min(double a, double b) {
  return a < b ? a : b;
}

double recursive_min(double *data, unsigned n) {
  return n==1 ? data[0] : min(recursive_min(data, n/2), recursive_min(data + n/2, n - n/2));
}

int main() {
  double a[13] = {31.0, 26.0, 23.0, 15.0, 42.0, 23.0, 53.0, 28.0, 12.0, 40.0, 45.0, 20.0, 39.0};
 
  printf("%lf\n", recursive_min(a, 13));
}

Share this post


Link to post
Share on other sites

 

He wasn't asking for a solution.

 

But here's mine: ;)

#include <stdio.h>

double min(double a, double b) {
  return a < b ? a : b;
}

double recursive_min(double *data, unsigned n) {
  return n==1 ? data[0] : min(recursive_min(data, n/2), recursive_min(data + n/2, n - n/2));
}

int main() {
  double a[13] = {31.0, 26.0, 23.0, 15.0, 42.0, 23.0, 53.0, 28.0, 12.0, 40.0, 45.0, 20.0, 39.0};
 
  printf("%lf\n", recursive_min(a, 13));
}

 

But that would go into a infinite recursion on a zero sized array ;)  I was trying to keep mine a bit more readable.  I didn't notice he didn't want a solution, my apologizes, I will erase my post.

Share this post


Link to post
Share on other sites

But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

 

 

 

I was trying to keep mine a bit more readable.

 

I find mine readable, actually. It's only hard to read if you are not used to seeing ?:.

 

Is this better?

double recursive_min(double *data, unsigned n) {
  if (n==1)
    return data[0];
  return min(recursive_min(data, n/2),
             recursive_min(data + n/2, n - n/2));
}

Share this post


Link to post
Share on other sites

 


But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

Or you could check if n == 0, and return 0 if so?

Share this post


Link to post
Share on other sites


Or you could check if n == 0, and return 0 if so?

 

No! Defining the minimum of zero things to be zero is a very bad idea. It violates basic features that people expect, like the minimum of the union of two sets being the minimum of the minima of the sets (the property my code uses in the recursion, precisely).

Share this post


Link to post
Share on other sites

 


But that would go into a infinite recursion on a zero sized array ;)

 

True! There should probably be a comment indicating that n should be at least 1, and perhaps an assert.

 

But what is the minimum of zero things? It should probably be +Infinity, I guess...

 

 

 

I was trying to keep mine a bit more readable.

 

I find mine readable, actually. It's only hard to read if you are not used to seeing ?:.

 

Is this better?

double recursive_min(double *data, unsigned n) {
  if (n==1)
    return data[0];
  return min(recursive_min(data, n/2),
             recursive_min(data + n/2, n - n/2));
}

 

Sorry, I should've been more clear.  It was a joke.  Perhaps I should've written it in italics or comic san serif?

 

When I was in school we'd be given silly assignments like the OP posted.  I'd give an answer like you presented (ie. the proper solution) and inevitably get a mark deducted because the prof would say something like 'it doesn't handle zero sized arrays'.  Which is true, except that you can't define a zero sized array.  Course that would lead into a long discussion about use cases, with arguments like 'well perhaps a nullptr was passed' and I'd point out that the 'true' answer (that which the prof posted) didn't bother to check for that either.  It always ended up being a whole lotta nonsense the irony being that searching an array in C (or C++) by using a subdivide algorithm is one of the worst ways to do so.

 

And so ya, it was a smart-ass comment meant as a joke.

Share this post


Link to post
Share on other sites

Here's a tricky question:

 

When you compute the minimum of N things, whether you use the recursive version or the iterative version, you'll end up performing about N comparisons. How many comparisons are needed to compute both the minimum and the maximum?

Share this post


Link to post
Share on other sites

Here's a tricky question:

 

When you compute the minimum of N things, whether you use the recursive version or the iterative version, you'll end up performing about N comparisons. How many comparisons are needed to compute both the minimum and the maximum?

 

If you were the original poster I would suspect homework, but since you're not...

 

 

 

How many are needed depends on what you already know.

 

 

 

If you know the collection is already sorted you can use the endpoints. No comparisons are needed.

 

If the collection is unsorted and you already know the value but are searching for them in a collection, the average number of comparisons is 1/2 of the collection size and the worst case of comparisons is the full container size. Since you must do this for both minimum and maximum, will be N on average and 2N worst case.

 

If the collection is unsorted and the maximum and minimum are unknown then it requires a comparison against every element. The number of comparisons is equal to the number of elements in the collection minus one (the first element starts as the initial best value).  Since the problem's definition requires a test against every element, N-1 is the lowest bound on the number of comparisons for a single pass.

 

If you want both the minimum and maximum value it depends on if you are performing two operations or one. You will need two comparisons for each, one against the best known minimum and another against the best known maximum. A few microprocessors provide CPU instruction that performs both tests, and I'm not sure if you would count that as one comparison or two. Either way, for the situations game developers usually care about doing this on a single core and a flat array will be most efficient to simply walk the list; cache effects will come into play and a simple linear traversal will result in both the minimum number of comparisons and good clock time.

 

 

 

 

The minimum number of comparisons does not always equate to most efficient for a situation.

 

Most of us have multiple processors available. Large data sets that span multiple devices offer non-uniform memory speeds and parallel space options. You can exchange linear time and linear space for parallel time or parallel space for a small cost.

 

If multiple processors are available you can partition the work among the processors you might run a pass on each partition in parallel, gather the work together, and run a second pass against the results of each partition. Similarly there are SIMD instructions you could perform on a single processor. When access time is not constant, such as having terabytes of data spread across data tapes rather than disk drives, a similar partition may make sense. There are several algorithms such as QuickSelect that may make sense in those situations as you can exchange time and space in data processing. 

 

You will perform more comparisons in these cases but likely complete the search in less clock time. 

Edited by frob
Realized I needed a bit of clarification.

Share this post


Link to post
Share on other sites

I looked through your solutions which were far better than my code. (translated Alvaro's code to be able to read it) :P

 

The funny thing is that the last code which I posted only had one careless little mistake which it didin't make it work.

That was on line:  y = min_num(SubsectionB_T, k-n); where instead of n-k I had written k-n.

After I saw your code I took a look at my code to find out what did I do wrong. And after 1 min I found that little mistake.

I laughed so hard. :P

 

Anyways guys thanks for taking the time helping me out.

Now I will try to modify the code in order for the function to return where the min is located.

Share this post


Link to post
Share on other sites

The funny thing is that the last code which I posted only had one careless little mistake which it didin't make it work.


No, the last code you posted contained this piece:
 
void subsections(double T[], int n, int k, double SubsectionA_T[], double SubsectionB_T[])
{
	int i;
	int j = 0;
	for (i=0;i<k;i++)
		SubsectionA_T[i] = T[i];
	for (i=k; i<n; i++)
	{
		SubsectionB_T[j] = T[i];
		j++;
	}
}
Imagine n is 10, so k is 5 and SubsectionA_T and SubsectionB_T are arrays of length 5. When you write into SubsectionB_T, you do it with indices 5, 6, ...

I pointed this problem out in the edit of my first post.

[EDIT: Ahhh, no! You did use a different variable j, so the code is more or less correct. You are still making copies of the data, though. Anyway, sorry about that.] Edited by Álvaro

Share this post


Link to post
Share on other sites
I frob missed the trick:

You can process the elements two at a time, compare them and then only use the smaller of the two to try to update the minimum and only use the larger of the two to try to update the maximum. This requires about N*3/2 comparisons.

I am not making any claims about practical usability of this trick: It's just a neat little puzzle.

Share this post


Link to post
Share on other sites

I frob missed the trick:

You can process the elements two at a time, compare them and then only use the smaller of the two to try to update the minimum and only use the larger of the two to try to update the maximum. This requires about N*3/2 comparisons.

I am not making any claims about practical usability of this trick: It's just a neat little puzzle.

 

Meh, it is a micro-optimization in the part that doesn't dominate. My hunch is that the added branch would slow things down if you were worried about performance.

 

As mentioned, there are solutions that require zero comparisons. Keep the collection sorted in the first place and don't worry about it.

Share this post


Link to post
Share on other sites
No, it's not a micro-optimization: It's the solution to a brain teaser. I think I posed the question correctly. If you don't enjoy that kind of thing, that's OK. But trying to argue about the real-life complexities of the situation is missing the interesting mathematical curiosity that I was pointing at.

Share this post


Link to post
Share on other sites

So guys any ideas on how to make the code return except for the value also the [/size]position of min?


What part are you having a hard time with?

Share this post


Link to post
Share on other sites

The problem is that the index keeps changing during the recursions.

And I dont want to make a classical search in order to find where the min is located inside the A[10]. 

I wanna know if there is a solution on how to return the index without searching.

 

6z1w5u.png

Edited by shadowstep00

Share this post


Link to post
Share on other sites

The easy way is with just searching. Is there another more clever way?

#include <stdio.h>

double recursive_min(double T[], int n,int *index);

int main(){
	double T[10] = {4,50,-10,-6,7,-11.6,7,-1,8,-9};
	double min;
	int index;
	min = recursive_min(T,11,&index);
  
    printf("min = %g\n", min);
    printf("Index = %d\n",index);
	
}

double recursive_min(double T[], int n,int *index){
	int i;
	if (n == 1)	
		return T[0];
	else{
		double x = recursive_min(T,n/2,index);
		double y = recursive_min(T + n/2, n - n/2,index);
		if (x < y)
		{
			for (i = 0; i<=n/2; i++){
				if (T[i] == x) 
					*index = i;
		}
			return x;
		}
		else 
		{
			for (i =n/2 ; i<=n; i++){
				if (T[i] == y) 
					*index = i;
				}
			return y;
		}
	}
}
Edited by shadowstep00

Share this post


Link to post
Share on other sites
Sign in to follow this