Здравствуйте, Gradiens, Вы писали:
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
Здравствуйте, Marty, Вы писали:
M> Здравствуйте!
M>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).
Здравствуйте, landerhigh, Вы писали:
L>Здравствуйте, Gradiens, Вы писали:
M>>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
L>А вот с этого места можно поподробнее?
На этот вопрос у меня два ответа.
Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".
Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны (это ж надо регистры запушить в стек, параметр занести в регистр или стек, провести вызов, после произведенных вычислений вернуть все как было до вызова и вернуть управление вызывающему коду). В результате скорость будет отличаться на порядок.
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как?
DB>Думаю, что этот вопрос нормальный только есть в компании надо будет заниматься графикой или подобным.
Здравствуйте, alzt, Вы писали:
M>>>>Откуда дровишки? Такое не подумав брякнешь — ни в одну нормальную контору не возьмут C>>>Ну вызов функции все-таки не бесплатный. Компиляторы конечно могут и рекурсивные функции встраивать, но с ограничением по глубине рекурсии.
M>>Зато место на стеке бесплатное. Не надо ничего в куче выделять
A>Можно пример кода с рекурсией, где за счёт этого будет экономия.
Здравствуйте, Gradiens, Вы писали:
G>Во-первых, не очень опытные коллеги не всегда представляют вычислительную сложность реализуемого при помощи рекурсии решения. Результат: "ой, зависло".
Э... ты, наверное, хотел сказать, "ой упало"?
G>Во-вторых у рекурсии большие накладные расходы. Если взять надуманный пример расчета факториала в цикле, или с рекурсией, то количество операций умножения будет одинаково. Но для рекурсии накладные расходы для вызова методов офигенны
В мире существуют не только процессоры x86/x86_64.
G>В результате скорость будет отличаться на порядок.
Такие заявления слуедует подкреплять бенчмарками. А то есть мнение, что толкать регистры в стек полюбому выйдет быстрее обращения к памяти мимо процессорного кеша. Не гворя уже о том, что подготовка и поддержание структуры данных для итеративной обработки взамен простой рекурсии тоже обходится не бесплатно.
Здравствуйте, Gradiens, Вы писали:
M>>2) Есть два набора чисел (ни к чему физически не привязаны, просто числа). Допустим, по 1000 штук, плюс-минус. Производится суммирование и получается две суммы. Надо их сравнить. Как? G>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
Наверно не точно сформулировал, но я так понял, что нужно сравнить на равенство. Может в такой формулировке и кривовато звучит
Здравствуйте, Qulac, Вы писали:
Q>Здравствуйте, Gradiens, Вы писали:
G>>Здравствуйте, Marty, Вы писали:
G>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>>Но себеседование действительно странное.
Q>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
Ну не знаю.. у сферических чисел должен быть тип.
Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет.
Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому
Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.
Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) M>>Мой ответ: следить за стеком (глубиной рекурсии) — не устроил, собесед хотел что-то еще услышать, я не понял, что. Я сказал, что рекурсию можно развернуть в цикл, он мне сказал — это цикл, а я спрашивал про рекурсию
SaZ>Тут уже много написали, но может хотели очевидного? Рекурсия не инлайнится (рантайм рекурсия).
M>>1) Какие проблемы могут быть при рекурсии? (с формулировкой могу ошибится, но смысл, кая я его понял, такой) G>Кроме как проблемы переполнения стека еще типичная проблема быстродействия.
Это не так. Любую рекурсию можно заменить на итеративный алгоритм с использованием структуры данных стек. Только в большинстве случаев, эта структура данных стек будет реализована с использованием динамической памяти, что уже дороже, чем использовать программный стек, так как память надо выделять, освобождать. Можно реализовать стек и без постоянного выделения памяти, но тогда уже нужно потратить время на то, чтобы заранее оценить, какой размер такой структуры данных нужен.
В качестве упражнения, можешь попробовать реализовать quick-sort не рекурсивно. А потом реализовать quck-sort так, чтобы выделение памяти в куче происходило только один раз.
Здравствуйте, Gradiens, Вы писали:
G>Здравствуйте, Qulac, Вы писали:
Q>>Здравствуйте, Gradiens, Вы писали:
G>>>Здравствуйте, Marty, Вы писали:
G>>>Для начала надо определиться по типу чисел. Для сферических чисел в вакууме возможны проблемы переполнения, а также проблемы потери точности. Сравнивать их, понятно, надо в лоб: a < b. Проблемы могут быть только при суммировании. А вот какие именно и как их решать — зависит от типа чисел.
G>>>Но себеседование действительно странное.
Q>>А вот на это ни кто не обратил внимание, в задаче фигурируют просто числа, т.е. "сферические числа в вакууме".
G>Ну не знаю.. у сферических чисел должен быть тип. G>Например, Int32. Тогда в качестве переменной суммы используем Int64 — и никаких проблем в принципе не будет. G>Или, тип чисел в массиве Int64. Тогда для суммы Int64 использовать нельзя, а вдруг переполнится. Надо использовать какой-нить BigInteger (я — дотнетчик, на других платформах должны быть аналоги, ну или их придется писать самому G>Если же у нас тип чисел — double — то может быть две проблемы. Переполнение, а также потеря точности при суммировании большого и маленького числа.
G>Но все равно, не бывает сферических чисел без физического смысла. А также не могу представить себе ситуацию, когда надо выполнить 10^100 + 10^-100. Даже если сложить диаметр вселенной (самое большое что есть в природе) с Планковской длиной (самое маленькое что есть в природе) — и то менее внушительный пример получится. Так что пример надуманный и годится только для затравки разговора, но никак не для реальных выводов.
"сферические числа в вакууме" у программистов и есть любой тип чисел.
По рекурсии я бы выделил три пункта:
1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека.
2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.
3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.
По числам с плавающей точкой, как тут уже сказали, сравнивать нужно по модулю:
bool bEqual = fabs(dSum1 — dSum2) < dEpsilon;
Здравствуйте, Iso12, Вы писали:
I>По рекурсии я бы выделил три пункта: I>1. Глубина рекурсии, т.е. смотреть чтобы не было переполнения стека. I>2. Условие по выходу из рекурсии, т.е. оно должно 100 % выполняться.
Это уже какое-то собеседование на должность КО получается.
I>3. Эффективность, т.е. проверка на повторяемость вычислений (действий). Если одни и те же вычисления повторяются много раз, то рекурсию применять не стоит.
То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?
То что я имел ввиду, это например вычисление чисел Fibbonachi:
fib (0) = fib (1) = 1
fib (n) = fib (n – 1) + fib (n – 2), n = 2, 3, ...
L>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя?
Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.
I>То что я имел ввиду, это например вычисление чисел Fibbonachi:
А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?
L>>То есть если программа только и делает, что занимается обходом деревьев, то делать это рекурсивно нельзя? I>Тут всё зависит от того, что мы хотим получить: скорость выполнения или простоту кода. Если время выполнения критично и есть алгоритм, который это делает быстрей без рекурсии, то рекурсия здесь не уместна.
Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.
L>А можно пример не из учебника или арсенала К.О, а встречающийся в реальной жизни?
В математических вычислениях часто встречается.
Что означает К.О. ?
L>Я приготовился записывать алгоритм обхода дерева без рекурсии, который по производительности превзойдет вариант с рекурсией.
Если алгоритм с рекурсией самый быстрый и стек позволяет, то его и используйте. Код от этого будет проще и читабельней. Всему своё место. Или вы понимаете слово "Эффетивность" как-то по другому?
