Help needed inorder to avoid recursion

Question

Hello All I have a method, which gives me the required number of Boxes based on number of devices it can hold.Currently i have implemented this logic using recursion

private uint PerformRecursiveDivision(uint m_oTotalDevices,uint m_oDevicesPerBox, ref uint BoxesRequired)
        {
            if (m_oTotalDevices< m_oDevicesPerBox)
            {
                BoxesRequired = 1;
            }
            else if ((m_oTotalDevices- m_oDevicesPerBox>= 0) && (m_oTotalDevices- m_oDevicesPerBox) < m_oDevicesPerBox)
            {
                //Terminating condition
                BoxesRequired++;
                return BoxesRequired;
            }
            else
            {
                //Call recursive function
                BoxesRequired++;
                return PerformRecursiveDivision((m_oTotalDevices- m_oDevicesPerBox), m_oDevicesPerBox, ref BoxesRequired);
            }
            return BoxesRequired;
        }

Is there any better method to implement the same logic without using recursion. Cos this method is making my application very slow for cases when number of devices exceeds 50000.

Thanks in advance for your support Constant learner

Answer 1

Yes, you can use Queue to avoid the recursion. Smth like this:

    private void ProcessNonRecursively(string data)
    {
        Queue<string> queue = new Queue<string>();

        // Enque initiali data.
        queue.Enqueue(data);

        while (queue.Count > 0)
        {
            // Get current data.
            string currentData = queue.Dequeue();

            // Process it here...

            // Enque all data to be processed instead of calling the recursion.
            foreach (string newData in someNewDataAfterProcessing)
            {
                queue.Enqueue(newData);
            }
        }
    }

But it looks like in your case you don't need recursion/queue at all. See other answers.

Answer 2

How about this:

int boxesRequired = m_oTotalDevices / m_oDevicesPerBox;
if (m_oTotalDevices % m_oDevicesPerBox > 0)
    boxesRequired++;

return boxesRequired;

I don't see why you would use recursion or even a queue based solution for something like this.

Answer 3

I think I must be misunderstanding. If you need to determine how many boxes are needed to hold a given number of devices, it's trivial:

boxesRequired = ceil(totalDevices / devicesPerBox)

...where ceil is an operation that takes any fractional value and rounds up to the nearest integer. (Nearly all environments have that operation. Just noticed your .Net tag; it's Math.Ceiling in .Net; if you're using JScript.Net it's also Math.ceil because that's a standard part of JavaScript.)

If you need to do it purely with integer math:

boxesRequired = totalDevices / devicesPerBox
if totalDevices mod devicesPerBox <> 0 then
    increment boxesRequired
endif

Answer 4

It is quite likely that your compiler have already transformed this tail recursion into a loop.

Answer 5

Cos this method is making my application very slow for cases when number of devices exceeds 50000.

Have you profiled this? I find that highly unlikely. There’s nothing there to make the computation slow.

Another thing: the use of ref in your case is completely unnecessary and inappropriate.