C - Управление стеком вызовов в рекурсивных методах

Я новичок здесь, и у меня есть проблема, которая прослушивает меня. Я начинающий, поэтому, пожалуйста, не смейтесь надо мной. Я хочу, чтобы рекурсивная быстрая сортировка работала на большом количестве элементов, скажем, 100000. Я знаю, что это приведет к переполнению стека. В течение последних нескольких дней я искал поисковые запросы, пытаясь найти способ управления стеком вызовов. не может действительно найти хороший источник информации. My ideea - удалить обратный адрес каждого рекурсивного вызова, кроме последнего, который вернется к первому вызову функции. Я не знаю, возможно ли это или если это другое решение для этой проблемы.C - Управление стеком вызовов в рекурсивных методах

P.S. : Я хочу, чтобы quicksort был рекурсивным.

Извините, если мои проблемы выглядят глупо, но я могу уговорить любой подходящий ответ. Извините за мой плохой английский. Спасибо!

источник

2012-04-03 user1311596

Опубликовать код. Если рекурсия может быть вызвана хвостом, вы можете заставить ее работать. –

Две вещи, которые помогут; не используйте наивный метод при выборе стержня и всегда возвращайтесь к меньшему разделу. – Blastfurnace

Если вы выберете подходящий стержень, вы исчерпаете память задолго до того, как глубина рекурсии станет проблемой. Тогда глубина логарифмична по размеру массива. –

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

источник

2012-04-03 23:34:22 stefanB

Я понимаю, что лучше избегать рекурсии, но можно ли решить эту проблему и использовать рекурсивный метод? – user1311596

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

Таким образом, невозможно удалить обратные адреса каждого рекурсивного вызова, кроме первого рекурсивного вызова, который я буду хранить в переменной и последнем возвратном вызове, который возвращает адрес, который я хочу поменять с адресом первого вызова. Извините еще раз за мой глупый вопрос, но я устал и разочаровываюсь в том, что не нахожу ответа на этот вопрос. Спасибо снова! – user1311596

Если пространство стека является проблемой, а памяти в общем случае нет, вы можете легко преобразовать рекурсивную реализацию в итеративную, используя собственный кластер, выделенный для кучи. То есть вместо того, чтобы делать вызов рекурсивной функции, нажмите нужные вам аргументы в свою собственную структуру данных стека. Затем вы можете перебирать свой стек и обрабатывать каждый набор аргументов.

источник

2012-04-03 23:41:03 jamesdlin

Обратите внимание, что 100000 элементов в массиве - ничто; это приведет лишь к вложенным вызовам 17 функций глубоким:

$ echo "l(100000)/l(2)" | bc -l 
16.60964047443681173951

Это log(N)/log(2) - log(2) для преобразования его логарифма 2.

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

источник

2012-04-03 23:44:48 sarnold

похоже, что вы пытаетесь выполнить рекурсию хвоста, о которой шла речь здесь;

Tail recursion in C

источник

2012-04-04 08:41:35 sardok

C - Управление стеком вызовов в рекурсивных методах

ответ

Смежные вопросы