Recursion

[MoGuL]

I'm trying to split a binary (only elements are 0 and 1) dynamically allocated 3D array into seperate and smaller 3D arrays. The following figure makes it a bit clearer to understand:

http://img521.imageshack.us/img521/4296/splittingsteps.png

It's a sparse 3D array of 10.000 elements. For each '1' that is an element of my array, I want to create a unique bitstream. The obtained subdomains return me a number of 1s that are in the corresponding block. That number is then converged to binary and added to the bitstream

Since this splitting operation is the same every time, first splitting in the i direction, then in the j direction and then in the k direction (3 levels) I want to do this recursively. Also, since I'm working in ANSI C, working non recursively would result in a huge amount of duplicate code.

The splitting should terminate at subdomains that are empty, so only containing 0 (number_x =0) or when the size is [0..1] x [0..1] x [0], those are coded differently, husing a Huffman code...

My current code for the first three levels can be found at:

http://codepad.org/zGbAhKrC

Anyone who can help me with some pseudo code based on my current code?

Thanks in advance!

[KunjeeB]

Can you please define what are the steps involved in splitting a single block (hope I'm understanding you coreectly so far)

[MoGuL]

It's a 3D array with dimensions:

I = [0 .. 511] x [0 .. 511] x [0 .. 31]

Split level #1 results in two 3D arrays of dimensions:

I_w = [0 .. 255] x [0 .. 511] x [0 .. 31]
I_e = [256 .. 511] x [0 .. 511] x [0 .. 31]

number_w = 6505 and number_e = 3495 represent the number of 1's in both parts.

Split level #2 results in four 3D arrays of dimensions:

I_sw = [0 .. 255] x [0 .. 255] x [0 .. 31]
I_nw = [0 .. 255] x [256 .. 511] x [0 .. 31]
I_se = [256 .. 511] x [0 .. 255] x [0 .. 31]
I_ne = [256 .. 511] x [256 .. 511] x [0 .. 31]

number_sw = 2141 and number_nw = 4364 represent the number of 1's in the corresponding block.
number_se = 1745 and number_ne = 1750 represent the number of 1's in the corresponding block.

Split level #3 results in eight 3D arrays of dimensions:

I_swm = [0 .. 255] x [0 .. 255] x [0 .. 15]
I_nwm = [0 .. 255] x [256 .. 511] x [0 .. 15]
I_swp = [0 .. 255] x [0 .. 255] x [16 .. 31]
I_nwp = [0 .. 255] x [256 .. 511] x [16 .. 31]
I_sem = [256 .. 511] x [0 .. 255] x [0 .. 15]
I_nem = [256 .. 511] x [256 .. 511] x [0 .. 15]
I_sep = [256 .. 511] x [0 .. 255] x [16 .. 31]
I_nep = [256 .. 511] x [256 .. 511] x [16 .. 31]

number_swm = 2141 and number_swp = 0 represent the number of 1's in the corresponding block.
number_nwm = 4364 and number_nwp = 0 represent the number of 1's in the corresponding block.
number_sem = 1745 and number_sep = 0 represent the number of 1's in the corresponding block.
number_nem = 1750 and number_nep = 0 represent the number of 1's in the corresponding block.

Now I want to repeat the above steps recursively for each obtained block in the last step until I have only a 1x1x1 array left or all zero arrays...

[KunjeeB]

I think I grasp the general pattern of your logic and can see us ending up with a vector of 1X1X1 arrays.

The number of 1x1x1 array items in the vector should be equal to the number of items in your original array.

It would then appear that we could have achieved the same result without recursion by iterating through each item of original array and associating the number of binary 1's in per item.

What other reason are you wanting to use recursion to solve this - please excuse me if I don't understand you and correct me accordingly.

[MoGuL]

Well, it's actually an encoding scheme. For each 1 that is an element of my initial 3D array, I want to create a unique bitstream. The obtained subdomains return me a number of 1s that are in the corresponding block. That number is then added to the bitstream by converting it to binary.

[MoGuL]

Anyone? Kinda stuck with this...