Как я могу выйти из рекурсивной функции?
Я работаю над программой, которая работает с рекурсивной функцией.
Моя проблема заключается в том, что когда работа рекурсивной функции завершена, и управление передается следующей функции, она возвращается обратно к рекурсивной функции после завершения работы следующей функции.
Мне нужен какой-то код, который мог бы принудительно передать управление обратно в функцию. Я не хочу выходить из своей программы.
Каждый раз, когда я звоню function1 , я выполняю некоторые изменения в переменных a и num . Но проблема в том, что при определенных условиях, когда function2 называется управление передается function1 очередной раз. Не могли бы вы предоставить мне какой-нибудь код, чтобы предотвратить это? Это часть генератора расписания, который я разрабатываю.
Как полностью выйти из функции с рекурсией и циклом бесконечной вложенности?
Есть функция, которая с использованием рекурсии перебирает элементы массива неограниченной вложенности на соответствие определённому критерию. Обнаружив первый попавшийся элемент, соответствующий критерию, функция должна тут же вернуть 1.
Проблема в том, что из-за рекурсии, если я пишу return 1, значение возвращается в «родительскую» копию функции, и цикл продолжается. Если я пишу break 1/2/3/4 и т. д.- я завершаю лишь конкретный цикл, по вложенности относительно текущего, а у меня их может быть хоть миллион. Есть какая-то возможность скомандовать остановку всех циклов и возвращение значения 1?
Пока нашел только проверку значения возвращаемого вызванной копией — если 1, то все вложенные копии возвращают родителю 1, пока не дойдёт до самой первой.
Есть ли какое-то универсальное решение, которое останавливает самый первый цикл (break) или команда остановки самой первой копии функции (return)?
Exit the entire recursion stack
I’m calling a function fooA from main() that calls another function fooB that is recursive. When I wish to return, I keep using exit(1) to halt execution. What is the right way to exit when the recursion tree is deep?
Returning through the recursion stack may not be of help because returning usually clears a part solution I build and I don’t want to do that. I want to do execute more piece of code from main().
I read Exceptions can be used, it would be nice if I can get a code snippet.
2 Answers 2
The goto statement won’t work to hop from one function back to another; Nikos C. is correct that it wouldn’t account for releasing the stack frames of each of the calls you’ve made, so when you got to the function you goto’ed to, the stack pointer would be pointing to the stack frame of the function you were just in. no, that just won’t work. Similarly, you can’t simply call (either directly, or indirectly via a function pointer) the function you want to end up in when your algorithm is done. You’d never get back to the context you were in prior to diving into your recursive algorithm. You could conceivably architect a system this way, but in essence each time you did this you’d «leak» what was currently on the stack (not quite the same as leaking heap memory, but a similar effect). And if you were deep into a highly recursive algorithm, that could be a lot of «leaked» stack space.
No, you need to somehow return back to the calling context. There are only three ways to do so in C++:
- Exit each function in turn by returning from it to its caller backing up through the call chain in an orderly fashion.
- Throw an exception and catch it at the point right after you launched into your recursive algorithm (which automatically destroys any objects created by each function on the stack in an orderly fashion).
- Use setjmp() & longjmp() to do something similar to throwing & catching an exception, but «throwing» a longjmp() will not destroy objects on the stack; if any such objects own heap allocations, those allocations will be leaked.
To do option 1, you have to write your recursive function such that once a solution is reached, it returns some sort of indication that it’s complete to its caller (which may be the same function), and its caller sees that fact & relays that fact on to its caller by returning to it (which may be the same function), so on and so on, until finally all stack frames of the recursive algorithm are released and you return to whatever function called the first function in the recursive algorithm.
To do option 2, you wrap the call to your recursive algorithm in a try <. >and immediately after it you catch() <. >the expected thrown object (which could conceivably be the result of the computation, or just some object that lets the caller know «hey, I’m done, you know where to find the result»). Example:
. and in your recursive function, when you finish the results, you simply:
. and in your recursive function, when you finish the results, you simply:
Выйти из рекурсивной функции, когда динамическое условие выполнено
Я хотел бы выйти из рекурсивной функции и вернуться к функции вызывающего, когда возникает определенное условие (если оно возникает). Так что моя рекурсивная функция — слышать голоса, которые могут сказать ей, чтобы она ушла!
Бывает только после 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 состояние.