Logic error with recursion to find smallest in an array

aijazbaig1 · #1 19-Jun-2006, 04:09

Huy.
I am using recursion to find the smallest number in a given array. To keep it simple I have fixed the array length at 6.
Heres my code. (I am using Visual C++ version 6)

CPP / C++ / C Code:

#include <stdio.h>
#define SIZE 6

int find_smallest(int array[]);

int main()
{
int arr[] = {1,5,3,4,8,6};
int smallest;
smallest = find_smallest(arr);
printf("the smallest number in the array is %d\n",smallest);
return 0;
}

int find_smallest(int array[])
{

static int progress_marker = 0;
register int smallest;


if (progress_marker >= SIZE-2)
{
if (array[SIZE-2] > array[SIZE-1])
smallest = array[SIZE-1];
else smallest = array[SIZE-2];
return smallest;
}
else
{
++progress_marker;
find_smallest(array+progress_marker);
}
}

I doubt if the static variable is playing foul here..nonetheless id appreciate if some gurus would lend me a helping hand albeit virtually..

Sirk · #2 20-Jun-2006, 14:22

I see a couple of things you'll need to change.

1) Each time you call the recursive function you are passing an array that is a little bit shorter then the last time you called. For example the first time you call it the entire array gets passed:

{1,5,3,4,8,6}

You then increment progress_marker and pass (arr+progress_marker), so the second call you are really passing this:

{5,3,4,8,6}

Now when you call find_smallest(arr+progress_marker) for the 3rd time,progress_marker=2 so {5,3,4,8,6} + 2 will actually send:

{4,8,6} (Notice how 3 gets skipped)

The next call sends {4,8,6} + 3 which actually jumps outside of your original array!!

Change this line:

find_smallest(arr+progress_marker);

to

find_smallest(arr+1)

2) You never actually set smallest to anything unless this line is true:

CPP / C++ / C Code:

if (array[SIZE-2] > array[SIZE-1])

In side your else you need something like:

CPP / C++ / C Code:

  if (arr[0] < smallest)
    smallest = arr[0];

And you would then need to change smallest to be a static.

Give those changes a try, and repost if you still have any issues.

aijazbaig1 · #3 27-Jun-2006, 09:53

Hi.
I have tried the following recursive version and it works fine

(as long as no two elements have the same value )

CPP / C++ / C Code:

#include <stdio.h>
#define SIZE 6

void printarray(const int [],const int ); 
int recur_min(const int *array);

int main()
{
	int array[SIZE],i,smallest;
	printf("enter the elements of the array and press enter after entering each element\n");
	for (i=0;i<=SIZE-1;i++)
		scanf("%d",&array[i]);
	array[SIZE]='\0';
	printarray(array,SIZE);
	smallest = recur_min(array);
	printf("the smallest in the array is %d\n",smallest);
	return 0;
}

void printarray(const int array[], const int size) 

{ // Print array on standard output ----------------------------------------
	int i;
	printf("\n");
	for (i=0;i<size; i++)
		printf("%d\n",array[i]);
	printf("\n");
}

int recur_min(const int *array)

{
	static int smallest;
	if ( *(array+2) != '\0')
	{
		smallest = recur_min(array+1);
		if (*array < smallest) smallest = *array;
		return smallest;
	}
	else
	{
		if(*array < *(array+1))
			smallest = *array;
		else
			smallest = *(array+1);
		return smallest;
	}
}

However it generates a windows error which says it needs to close the non responsive program i.e. the exe file of the project

I am using VC++ version 6.0 as u guys already know. Can somebody explain why? Is it because of stack overflow?

but isnt this program a lil too small for that.

I would appreciate any insights from u guys.

Best Regards,
Aijaz Baig.

Sirk · #4 27-Jun-2006, 10:52

When you declare an array and you are going to use the '\0' to terminate it, you have to make sure to add 1 more to the size of your array.

When you do:
#define SIZE 6
int array[SIZE]

You get an array that has been allocated 6 spaces (0-5) like this:
array[0]
array[1]
array[2]
array[3]
array[4]
array[5]

When you then try and do array[SIZE]='\0', you are actually writing one past the end of your array, because SIZE is 6. So array[6]='\0'.

Simply change
int array[SIZE] to int array[SIZE+1]

rajamca · #5 13-Jul-2006, 08:32

i did it using following program, it returns smallest number among the array elements.

CPP / C++ / C Code:

#include <stdio.h>

int small(int a[])
{
	static int i;
	int s;

	s=a[i];
	
	if(++i==6)
		return s;

	if(s>a[i])
		s=a[i];
	
	a[i]=s;
	small(a);
}

void main()
{
	int arr[6]={14,12,16,8,18,13};
	int sm;
	sm=small(arr);

	printf("small number = %d\n",sm);
}

Regards,

Raja.P

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Need help deleting the last element in the array	headphone69	C++ Forum	2	15-Mar-2006 19:31
I'm New - ARRAY question!	NewBieFemAle	Java Forum	3	07-Dec-2005 02:56
How do you find the return address in an array of integers?	racermike1967	C Programming Language	2	07-Nov-2005 10:08
template comiling problems - need expert debugger!	crq	C++ Forum	1	01-Feb-2005 21:26
Creating N string	gwk	C Programming Language	3	20-Jul-2004 23:27

Logic error with recursion to find smallest in an array

Re: Logic error with recursion to find smallest in an array

Re: Logic error with recursion to find smallest in an array

Re: Logic error with recursion to find smallest in an array

Re: Logic error with recursion to find smallest in an array