Должен ли я избегать рекурсии на iPhone?

Question

Должен ли я избегать рекурсии с кодом, который работает на iPhone?

Или по-другому, кто-нибудь знает максимальный размер стека на iphone?

Answer 1

Да, избегая рекурсии, это хорошо на всех встроенных платформах.

Не только снижает или даже снижает вероятность переполнения стека, но также дает быстрый код.

Вы всегда можете переписать рекурсивный алгоритм как итеративный. Это не всегда практично (думаю, quicksort). Способ обойти это - переписать алгоритмы таким образом, чтобы глубина рекурсии была ограничена.

Интросор - прекрасный пример того, как это делается на практике. Он ограничивает глубину рекурсии в быстродействующей сортировке log2 (число элементов). Таким образом, на 32 битной машине вы никогда не рекурсию глубже, чем 32.

http://en.wikipedia.org/wiki/Introsort

Я написал довольно много программного обеспечения для встраиваемых платформ в прошлом (автомобильных развлекательных систем, телефонов, игровых консолей-и тому как), и я всегда убедился, что я поставил верхний предел на глубину рекурсии или, во-первых, избегал рекурсии.

В результате ни одна из моих программ никогда не умирала с переполнением стека, и большинство программ довольны 32kb стека. Это окупается, когда вам нужно несколько потоков, поскольку каждый поток получает свой собственный стек. Вы можете сохранить мегабайты памяти таким образом.

Answer 2

Максимальный размер штабеля на iphone?

iPhone запускает модифицированный OSX, в котором каждому процессу предоставляется допустимое пространство памяти, как и в большинстве операционных систем.

Это полный процессор, поэтому стек растет, а куча растет (или наоборот в зависимости от вашей перспективы). Это означает, что вы не будете переполнять стек до тех пор, пока не закончите память, выделенную вашей программе.

Лучше всего избегать рекурсии, когда вы можете использовать стек и производительность (вызовы функций дороги, относительно простых циклов), но в любом случае вы должны решить, какие ограничения вы можете разместить на рекурсивных функциях, и усечь их, если они слишком долго.

Answer 3

Я вижу пару ответов, которые сводятся к «не использовать рекурсию». Я не согласен - это не похоже на то, что iPhone - это жесткая встроенная система. Если проблема по своей сути рекурсивна, не стесняйтесь ее выражать таким образом.

Если вы не переходите к глубине стека в сотни или тысячи кадров, у вас никогда не будет проблемы.