Как выходить из глубокой рекурсии, если не с помощью GOTO?
Допустим, искал я что-то рекурсивно. Нашёл. Глубина рекурсии может быть более 10-20 вызовов.
Как выйди оттудова? Такое ли goto зло?
ничего не понял.
я сейчас говорю про JS.
единственное что приходит на ум, это
горшочек масла
> единственное что приходит на ум, это
И чем этот способ не устраивает?
Хотя строчка с "stop" непонятно зачем, вроде изначально ее не было.
горшочек масла
> Как выйди оттудова? Такое ли goto зло?
Единственный способ выхода из рекурсии — раскрутить ее в обратную сторону. Метка оператора goto должна быть объявлена в той же области видимости, где вызывается:
Поэтому использовать goto для решения проблемы не удастся.
горшочек масла
> Глубина рекурсии может быть более 10-20 вызовов. Как выйди оттудова? Такое ли goto зло?
Вызвать return конкретное_значение;
При этом конкретное_значение на всех уровнях рекурсии означает, что пора бы выйти с этим же значением return конкретное_значение;
заменить рекурсию на свой стек, нашел результат — очистил стек.
Радует, что большинство не советует кинуть исключение)
Сишечка не может в хвостовую рекурсию, потому вернуть заранее оговоренное значение либо кинуть исключение.
Если твой язык умеет хвостовую рекурсию тогда просто вернуть что-нибудь, рекурсия закончится без глубокого въезда в стек.
http://ru.wikipedia.org/wiki/Хвостовая_рекурсия
kvakvs
> Сишечка не может в хвостовую рекурсию
Если оптимизатор осилит, то может.
kvakvs
Как способ возврата значения влияет на максимальную глубину стека?
TarasB
> Как способ возврата значения влияет на максимальную глубину стека?
Если ты прочёл ссылку, то при хвостовой рекурсии стек не растёт в глубину. Или растёт медленно, если не все рекурсивные вызовы — хвостовые.
kvakvs
Студент пришёл на экзамен, выучив только главу про червей.
— Итак, молодой человек, покажите ваш билет. Так, слоны, расскажите-ка про слонов.
— Слон это такое млекопитающее с хвостом, хвост похож на червя. Черви живут под землёй, питаются. (итд)
Так вот, к чему это я? А, вот, к чему вообще тут хвостовая рекурсия? Изначальный вопрос никакого отношения к ней не имеет, и способ написания выхода из вложенного вызова тоже не зависит от того, какие оптимизации умеет делать компилятор.
TarasB
> Как способ возврата значения влияет на максимальную глубину стека?
Как черви влияют на слонов?
Никак не влияет. Можно весь стек сожрать и крашнуться.
Как полностью выйти из функции с рекурсией и циклом бесконечной вложенности?
Есть функция, которая с использованием рекурсии перебирает элементы массива неограниченной вложенности на соответствие определённому критерию. Обнаружив первый попавшийся элемент, соответствующий критерию, функция должна тут же вернуть 1.
Проблема в том, что из-за рекурсии, если я пишу return 1, значение возвращается в «родительскую» копию функции, и цикл продолжается. Если я пишу break 1/2/3/4 и т. д.- я завершаю лишь конкретный цикл, по вложенности относительно текущего, а у меня их может быть хоть миллион. Есть какая-то возможность скомандовать остановку всех циклов и возвращение значения 1?
Пока нашел только проверку значения возвращаемого вызванной копией — если 1, то все вложенные копии возвращают родителю 1, пока не дойдёт до самой первой.
Есть ли какое-то универсальное решение, которое останавливает самый первый цикл (break) или команда остановки самой первой копии функции (return)?
Выйти из рекурсивной функции, когда динамическое условие выполнено
Я хотел бы выйти из рекурсивной функции и вернуться к функции вызывающего, когда возникает определенное условие (если оно возникает). Так что моя рекурсивная функция — слышать голоса, которые могут сказать ей, чтобы она ушла!
Бывает только после str печатается здесь:
Как это сделать (прекратить развертывание рекурсии и вернуться к функции вызывающей стороны)?
просто кажется, чтобы заблокировать выполнение и никогда не закончится!
PS — меня интересует даже с старые методологии.
Решение
Чтобы выразить это в простейшей форме, вы можете сделать что-то вроде этого:
Затем вы начинаете рекурсию:
В вашем случае вы можете прервать рекурсию
Установка в true выведет вас из всего дерева вызовов.
Вы также можете сделать это в C, просто используя указатель, а не ссылку.
Другие решения
Простое решение, учитывая, что ваша функция в настоящее время не имеет возвращаемого значения, состоит в том, чтобы использовать его, чтобы указать, было ли выполнено это условие завершения. Затем вы можете использовать его для немедленного выхода из всех рекурсивных вызовов, если результат станет истинным.
Не уверен, что я правильно фиксирую вашу ожидаемую логику, но интуитивно понятный подход будет примерно таким:
magic Функция вызывает себя рекурсивно в двух местах. Таким образом, в каждом из этих мест, вы должны проверить состояние вашего выхода. Ответ, данный Пэдди, детализирует это.
Альтернативой для немедленного раскручивания стека является использование setjmp а также longjmp который может функционировать как нелокальный goto ,
setjmp функция возвращает 0 когда вызывается напрямую. когда longjmp называется, это setjmp функция, которая на самом деле возвращает, а возвращаемое значение является вторым параметром, данным longjmp ,
Здесь у нас есть функция-обертка, которая вызывает setjmp , Это устанавливает точку скачка для когда longjmp называется. Затем вызывается рекурсивная функция. Позже, когда рекурсивная функция «слышит голоса», приказывая ей выйти сейчас, это вызывает longjmp который сразу идет прямо в соответствующий setjmp вызов.
Эти функции определены как в C99, так и в POSIX, поэтому система, соответствующая POSIX (т.е. Linux), должна по-прежнему иметь их в режиме C89.
Если бы вы делали это в C ++, предпочтительным методом было бы генерировать исключение в рекурсивной функции и перехватывать его в функции-обертке.
Это нерекурсивный вариант. По сути, он генерирует все увеличивающиеся последовательности 0 <= a[0] < . < a[dist-1] < strlen(num) и возвращает биты в соответствующих индексах.
Который можно использовать так:
Постскриптум Благодаря @ruakh для упоминания отсутствующей оптимизации в while — if состояние.