Как избежать рекурсии

Question

У меня есть метод, который дает мне необходимое количество ящиков в зависимости от количества устройств, которые он может содержать. В настоящее время я реализовал эту логику с помощью рекурсии

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;
        }

Есть ли какой-нибудь лучший способ для реализациита же логика без использования рекурсии.Потому что этот метод делает мое приложение очень медленным для случаев, когда количество устройств превышает 50000.

Answer 1

Как насчет этого:

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

return boxesRequired;

Я не понимаю, почему вы бы использовали рекурсию или даже решение на основе очереди для чего-то подобного.

Answer 2

Я думаю, что я неправильно понимаю. Если вам нужно определить, сколько ящиков необходимо для хранения данного количества устройств, это тривиально:

boxesRequired = ceil(totalDevices / devicesPerBox)

... где ceil - операция, которая принимает любое дробное значение и округляет до ближайшего целого числа. (Практически во всех средах есть такая операция. Только что заметил ваш тег .Net; он Math.Ceiling в .Net; если вы используете JScript.Net, он также Math.ceil, потому что это стандартная часть JavaScript. )

Если вам нужно сделать это чисто с помощью целочисленной математики:

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

Answer 3

Вполне вероятно, что ваш компилятор уже преобразовал эту хвостовую рекурсию в цикл.

Answer 4

Да, вы можете использовать Очередь, чтобы избежать рекурсии. Что-то вроде этого:

    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);
            }
        }
    }

Но, похоже, в вашем случае вам вообще не нужна рекурсия / очередь. Смотрите другие ответы.