Avoiding recursion

Question

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. Because this method is making my application very slow for cases when number of devices exceeds 50000.

Oded · Accepted Answer · 2010-03-15 08:59:15Z

3

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.

answered Mar 15, 2010 at 8:59

Oded

501k102 gold badges900 silver badges1k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

T.J. Crowder · Accepted Answer · 2010-03-15 09:06:29Z

2

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

edited Mar 15, 2010 at 9:06

answered Mar 15, 2010 at 8:59

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

Comments

Andrew Bezzub · Accepted Answer · 2010-03-15 09:02:05Z

0

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.

edited Mar 15, 2010 at 9:02

answered Mar 15, 2010 at 8:56

Andrew Bezzub

16.1k7 gold badges54 silver badges73 bronze badges

1 Comment

Konrad Rudolph Over a year ago

No, not a queue: a stack (in the general case).

SK-logic · Accepted Answer · 2010-03-15 09:05:35Z

0

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

answered Mar 15, 2010 at 9:05

SK-logic

9,7491 gold badge25 silver badges37 bronze badges

Collectives™ on Stack Overflow

Avoiding recursion

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related