Recursive 2D Array Functions

Page 1 of 1

3 Replies - 3246 Views - Last Post: 07 February 2010 - 04:36 PM Rate Topic: -----

#1 Guest_WTFsandwich*


Reputation:

Recursive 2D Array Functions

Posted 07 February 2010 - 11:36 AM

I'm required to make the following four functions to be calculated on a 2D array.

Sum(int[,] a, row, col) - Adds all elements together
Average(int[,] a, row, col) - Finds average value of elements
Max(int[,] a, row, col) - Finds maximum value
Min(int[,] a, row, col) - Finds minimum value

I have the sum function working correctly

public int Sum(int[,] a, int row, int col)
        {
            temp = 0;
            for (int m = row; m < a.GetLength(0); m++)
                temp += a[m, col];

            for (int m = col + 1; m < a.GetLength(1); m++)
                temp += a[row, m];

            if (row + 1 < a.GetLength(0) && col + 1 < a.GetLength(1))
            {
                temp += Sum(a, row + 1, col + 1);
            }

            return temp;
        }


What is giving me trouble is the Average function.

What I've attempted is to use the sum function, and simply divide it by the number of elements. However, because it is a recursive function, it will divide it every time it calls itself, giving an incorrect answer.

Here's my attempt at the average function.

public int Average(int[,] a, int row, int col)
        {
            temp = 0;
            for (int m = row; m < a.GetLength(0); m++)
                temp += a[m, col];

            for (int m = col + 1; m < a.GetLength(1); m++)
                temp += a[row, m];

            if (row + 1 < a.GetLength(0) && col + 1 < a.GetLength(1))
            {
                temp += Average(a, row + 1, col + 1);
            }

            return temp / (a.GetLength(0) * a.GetLength(1));
        }


Am I going about the whole function the wrong way or am I just failing to see where/how the division needs to be performed?

Is This A Good Question/Topic? 0

Replies To: Recursive 2D Array Functions

#2 Martyr2  Icon User is offline

  • Programming Theoretician
  • member icon

Reputation: 3873
  • View blog
  • Posts: 11,408
  • Joined: 18-April 07

Re: Recursive 2D Array Functions

Posted 07 February 2010 - 11:53 AM

Is there a requirement that these should be recursive? Typically what you do with these types of functions is make a nested loop. One for loop inside the other. This will give you the ability to find all the sums etc while also counting the number of elements along with it. Unless it was some kind of requirement, recursion is not really the ideal solution to this. It actually kills your performance and adds a complexity that you are now struggling with.

You will also see that the nested loop setup will help you greatly with the Min and Max functions. :)
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Guest*


Reputation:

Re: Recursive 2D Array Functions

Posted 07 February 2010 - 11:58 AM

Yes, they are required to recursive.

Also, it's very strange how the recursion is required to execute. It must take the first row and first column, then second row and second column, without the elements already accounted for etc etc until it gets to the last element.
Was This Post Helpful? 0

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 4888
  • View blog
  • Posts: 11,282
  • Joined: 16-October 07

Re: Recursive 2D Array Functions

Posted 07 February 2010 - 04:36 PM

Iterating over 2D arrays is kind of odd. It breaks the flow if recursion, to be honest. You're on the right track, in that you don't want to go over yourself again.

My solution would be to travel left and down if I'm in column 0, otherwise just left. This seemed to work in the least amount of code. I left in my debug code for you to play with...

int Sum(int[][] a, int row, int col) {
	if (row >= a.length || col >= a[row].length) { return 0; }
	// System.out.println("Sum(" + row + "," + col + ")");
	return a[row][col] + Sum(a, row, col+1) + ((col==0) ? Sum(a, row+1, col) : 0);
}

// int[][] data = {{1, 1, 1},{1, 1, 1},{1, 1, 1}};
// System.out.println( Sum(data,0,0) );


For your average, use row and col equals zero as your guide. You'll need to count in Average and then call sum. Min and max should be pretty simple.

Hope this helps.
Was This Post Helpful? 0
  • +
  • -
Page 1 of 1