Question

Need help with recursion in C++ Suppose you have a M*N Grid with some values. How do you compute all squares possible from the grid and find all possible sum of elements inside the sqaure.
Eg if we have 1 1
1 1
Then all possible sums are 1 and 4

Answer 1

1+1+1+1=4
how u got 1?

Answer 2

@Tomas

He meant the possible values of the sum of elements inside each square.

a square containing 1, and a square containing 4 squares (each containing one), is possible from the given example.

Answer 3

What is the sum of the elements of a square of sides M? It's the sum of the elements of the squares composing that square. You can probably decompose a big square into a number of smaller squares.

What is the sum of the elements of a square of sides 1? it's equal to the value of the single element inside that square.

Answer 4

I think it is possible to recursively slice a grid to decompose it into squares of size N, and then compute the sum of their elements (recursively :-D).

Answer 5

I think it would have to be a combination of iteration and recursion. It would be more of an iterative process to go through the largest squares that could be had from M x N, and those could be decomposed with a bactracking recursive function.

Answer 6

I got it without recursion but is it possible with recursion??

Answer 7

http://ideone.com/awyHK

It's in Python though.

The recursive function is the very last one in the Algorithms section of my code (Line 369, to be exact). It recursively computes the value of the possible squares of the grid: if the grid is not a square, then it breaks it into squares and computes their value recursively.

Answer 8

and also totals them up

Answer 9

My code is still mostly iterative though, but I'm sure there's an elegant recursive solution to tackle grid problems.

Answer 10

EDIT: now it actually prints the different values, instead of their sum :-P sorry http://ideone.com/xqXmX

Answer 11

If all of the squares have the same value, there is a much more elegant, recursive way to do it by slicing the grid into squares of size starting from the smallest dimension of the grid, and evaluating it's value.

Or you can be superflous and just say it's the value of the element multiplied by the size of the square.

Answer 12

for a grid where no element is unique, you have to be able to get out all the squares though

http://ideone.com/0nYu4 (my grid looks ugly)