recursion find number of times int appears in array...

[Johnny Steele]

Hi,

Who loves recursion?!?!?!?!

So, given an array of ints I need to recursively find the number of times a particular integer appears in that array. Like so:

public int numOf(int number, int[]a) {
		int index = 0;
		int count = 0;
		if(x.length > 0) {
			if(index < x.length) {
			   if(number == x[index]) {
				        count+= +1;
					index+= +1;
					return  count + index + numOf(number, a);
			   }else{
					index += +1;
					return count + index + numOf(number, a);
			   }
			}else{
				return count;
			}
		}else{
			return 0;
			}

This code is creating a huge stackOverFlow error when I unit test it. I am at a loss. I am allowed to use private helper methods although I am a bit confused as to how that would help in general or particular to this case. Regardless, any suggestions?

Thank you much

[Wouter Oet]

Why do you want to solve this problem with recursion?

[Johnny Steele]

my assignment requires it to be witten using recursion.

[anirudh jagithyala]

Hey Johnny,

Check out the below code.....This would work as far as i understood your requirement.

public int numOf(int number, int[]a) {
int count=0;


 if(a.length > 0)
        {int value=a[0];
    int a1[]=new int [a.length-1];
    
    if(number==value)
        count=1;

    for(int i=1;i<a.length;i++){
        a1[i-1]=a[i];
    }

    return count+numOf(number,a1);
}

 else
     return 0;

}

[Johnny Steele]

that seems to work!!! thank you very much!!! I did not think to use a for loop as in the past we've been told to avoid loops but not with this one.

thanks a lot!!!

[Matthew Brown]

The reason your original version didn't work is because you kept calling the method with the same arguments. Which means you got into an infinite loop - and eventually the stack runs out of memory and falls over.

If you're using recursion, you've got to make sure that the recursion is guaranteed to end at some point. Anirudh's version works because the array is one element shorter every time the method is called, so eventually you hit a zero length and the recursion stops.

[Carey Brown]

Your problem is a linear problem, recursion tends to be used on tree structures. This code uses recursion to subdivide an array a-la binary search, thereby artificially treating the problem as a tree.

import java.util.Random;

public class TryRecursion
{
	private static final int		SIZE = 42;
	private static final int		FIND = 7;
	private static final boolean	DEBUG = false;

	public static void main( String[] args )
	{
		int[]		ary = new int[ SIZE ];
		int		countRecursive, countLinear;
		Random	rand = new Random();

		for( int i = 0 ; i < ary.length ; i++ )
		{
			ary[ i ] = rand.nextInt( 10 );
			if( DEBUG )
				System.out.println( ary[i] );
		}

		countRecursive = recursive( ary, 0, ary.length, FIND );
		countLinear    = linear( ary, 0, ary.length, FIND );

		if( countRecursive == countLinear )
			System.out.println( "Success, count = " + countRecursive );
		else
			System.out.println( "Failed, recursive = " + countRecursive
				+ "  linear = " + countLinear );
	}

	private static int recursive( int[] ary, int start, int end, int find )
	{
		int		len = end - start;
		if( DEBUG )
			System.out.format( "start=%2d end=%2d\n", start, end );
		if( len <= 0 )
			return 0;
		if( len == 1 )
			return ary[ start ] == find ? 1 : 0;
		int		len2 = len / 2;
		return recursive( ary, start, start + len2, find ) + recursive( ary, start+len2, end, find );
	}

	private static int linear( int[] ary, int start, int end, int find )
	{
		int			count = 0;
		for( int i=start ; i < end ; i++ )
			if( ary[i] == find )
				count++;
		return count;
	}
}