Выход из рекурсивной функции?
Мне интересно, как выйти из рекурсивного цикла для основной функции. Я пытаюсь сделать простое упражнение палиндром. Функция должна возвращать True для «redivider», но возвращаемое True передается is_pal (), и функция не прерывается. Если не считать добавление второй переменной в is_pal для отслеживания True / False, как правильно выйти из этого рекурсивного цикла? Благодарю.
5 ответов
Таким образом, если они не совпадают, False возвращается; если он проходит весь путь до конца, возвращается True. Я также исключил излишнее условное выражение и проверил на случай ребра палиндрома четной длины.
Вам нужно вернуть False, если они не совпадают, и добавить оператор возврата. Также вы, вероятно, захотите проверить по len (str) == 0 и len (str) == 1:
Вы можете выйти из программы после печати результатов, используя функцию exit() .
Это не может быть хорошей практикой, но это может быть то, что вы ищете.
Один из способов выйти из рекурсивной функции в Python — это сгенерировать исключение и перехватить его на верхнем уровне. Некоторые люди скажут, что это не правильный способ думать о рекурсии, но он выполняет свою работу. Кроме того, если задача состоит в том, чтобы идентифицировать «проблемные» элементы в массиве / массиве массивов / ndarray и т. Д., Метод прерывания удобен, потому что он останавливает продолжение алгоритма после определения правильного глобального решения.
Вы пропускаете возврат. Также не используйте str в качестве имени переменной. Последнее, первая и последняя функции могут быть названы немного лучше.
Как остановить рекурсию Python
Я сделал функцию, которая рекурсивно ищет файлы, и я хочу, чтобы она остановила рекурсию при обнаружении первого файла:
4 ответа
Возвращает флаг, указывающий, был ли найден файл. Когда вы вызываете search_file , возвращайте, если возвращаемое значение равно True.
Вы близки. Вы уже нарушаете рекурсию, когда вы находите файл, проблема в том, что вы не пропедали этот результат, вплоть до цепочки. Хорошо сделанное выражение о печати показало бы, что пошло не так.
Обратите внимание, что вы должны иметь возможность возвращать ложную запись в случае, если она полностью отключится, не найдя ничего. Однако вы не хотите выходить из цикла for, если ничего не найдено в одном подкаталоге, не проверяя следующую вспомогательную директорию. Возврат выйдет из функции, возвращая результаты, не вводя перерыв.
С другой стороны, если вы хотите иметь только одно возвращение, вы можете использовать разрыв следующим образом
Я вижу проблему неспособности вернуть значение else: отличное от None в else: statement. Не могли бы вы предоставить более подробные сведения о том, что вы пытаетесь сделать?
Невозможно просто выйти из рекурсии при выполнении задачи. Каждый рекурсивный шаг, который был открыт, должен быть закрыт, прежде чем двигаться дальше. Функция должна возвращать что-то ( None или значение) своему вызывающему.
Я представляю, что это метод класса, который устанавливает значение для атрибута, потому что он не возвращает ничего, как только рекурсия началась. Вот что я сделал бы в том случае, если это метод класса.
Устранение рекурсии в Python
Привет, Хабр! Представляю вашему вниманию перевод статьи "Removing a recursion in Python, part 1" автора Эрика Липперта (Eric Lippert).
На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.
В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.
Недавний вопрос на StackOverflow заставил меня задуматься, как преобразовать рекурсивный алгоритм в итеративный, и оказалось, что Python довольно подходящий язык для этого.
Проблема с которой столкнулся автор вопроса заключалась в следующем:
- Игрок находится в произвольной клетке на пронумерованном поле;
- Цель вернуться в клетку №1;
- Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
- Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.
Вопрос заключается в следующем: какое наименьшее количество монет необходимо заплатить, чтобы вернуться из текущей клетки в первую.
Задача имеет очевидное рекурсивное решение:
Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?
Перед тем как мы начнем, хочу отметить, что конечно существуют более быстрые решения этой конкретной задачи, сама по себе она не очень интересна.
Скорее эта задача послужила лишь отправной точкой в вопросе, как в общем случае избавиться от единственного рекурсивного вызова в программе на Python.
Смысл в том, что можно преобразовать любой простой рекурсивный метод и избавиться от рекурсии, а это всего лишь пример, который оказался под рукой.
Техника, которую я собираюсь показать, конечно не совсем соответствует тому, как принято писать на Python, вероятно решение в Python-стиле использовало бы генераторы или другие возможности языка.
Что я хочу показать здесь, так это как избавиться от рекурсии, используя последовательность маленьких и безопасных преобразований, приводящих функцию к такой форме, в которой легко произвести замену рекурсии на итерацию.
Для начала давайте посмотрим как привести программу к такой форме.
На первом шаге нашего преобразования я хочу чтобы вычисления производимые до рекурсивного вызова сводились к вычислению аргумента, а вычисления, после рекурсивного вызова, производились в отдельном методе, который принимает результат рекурсивного вызова.
Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:
На третьем шаге, я хочу добавить вспомогательную функцию, которая будет выбирать функцию-продолжение, вызываемую после возврата из рекурсии.
Обратите внимание, что вспомогательная функция возвращает функцию.
Теперь запишем это в более общей и краткой форме:
Видно, что каждое проделанное изменение сохраняло смысл программы.
Сейчас проверка на чётность числа выполняется дважды, хотя до изменений проверка была одна.
Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.
Но давайте не будем беспокоиться об этом в рамках решения этой задачи.
Мы свели наш рекурсивный метод до максимально общей формы.
- В базовом случае:
- вычисляем значение, которое нужно вернуть;
- возвращаем его.
- вычисляем аргумент рекурсии;
- производим рекурсивный вызов;
- вычисляем возвращаемое значение;
- возвращаем его.
Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost .
Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.
Если у вас 2 и более рекурсии, то нам понадобится другое решение.
Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.
Хитрость в том, чтобы представить, что происходит в рекурсивной программе.
Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.
То есть, все вызовы get_argument происходят перед всеми вызовами after.
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:Больше никакой рекурсии!
Выглядит как магия, но все что мы здесь делаем — то же самое, что делала рекурсивная версия программы и в том же порядке.
Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!
Единственная полезная информация в стеке вызовов в рекурсивной версии программы — это какое значение имеет after, поскольку эта функция вызывается следующей, а все остальное на стеке не важно.
Вместо использования стека вызовов, как неэффективного и громоздкого способа хранения стека after, мы можем просто хранить стек функций after.
В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.
Breaking out of a recursive function?
I’m wondering how to break out of a recursive loop to the main function. I am trying to do a simple palindrome exercise. The function should return True for "redivider" but the return True is being passed to is_pal() and the function isn’t breaking. Short of adding a second variable to is_pal to track True/False, what is the proper way to break out of this recursive loop?
8 Answers 8
One way to break out of a recursive function in Python is to throw an exception and catch that at the top level. Some people will say that this is not the right way to think about recursion, but it gets the job done. Furthermore, if the task is to identify "problem" elements in an array/array of arrays/ndarray etc., a break technique is convenient, because it stops the algorithm from continuing after the global solution has been identified.
That way, if they don’t match, False is returned; if it makes it all the way to the end, True is returned. I also eliminated a redundant conditional and checked for the edge-case of an even-length palindrome.
You don’t "break" out of recursive functions. Trying to do so says you’re thinking about them the wrong way. Currently your recursive call is ignoring the output, which means that the recursion is pointless; whatever is_pal(middle(str)) returns has no effect on the return value of your function.
A recursive algorithm solves the input problem by decomposing the problem into a smaller problem, getting the solution to the smaller problem recursively, and then using the smaller solution to construct a correct solution to the larger problem. You don’t "break" out of the inner calls, you return a solution back up one level. You don’t know (or need to know) whether you’re in an inner call or a top level call. In either case, your function should do the same thing: return True if the argument is a palindrome, and False if it isn’t.
The algorithm you’re trying to implement is basically this:
- If the string is of length 1, it’s a palindrome (return True )
- Otherwise, if the first character is the same as the last character, then the input is a palindrome if the middle characters are a palindrome.
So what this means is that once you’ve established the first and last characters are the same, the answer to "is my input a palindrome" is exactly the same as the answer to "are the middle characters a palindrome". You need to return that answer to fulfil your contract. So the recursive call should be return is_pal(middle(str)) rather than just is_pal(middle(str)) . If this was a top level call, then that’s the answer; if this wasn’t a top-level call, then the outer call is going to need this answer to work out the answer to the outer problem (in this case, by simply returning it).
Btw, your algorithm also has some other problems.
You never return False , so the answer can never be False (in this case you happen to accidentally return None by falling off the end of the function if the first and last character don’t match, and None will probably do as a stand in for False in most cases, but it’s still not really correct).
If the string’s length is zero rather than 1 (which will happen if an empty string is passed in or if a palindrome of even length is passed in once all the pairs of equal first and last characters are stripped off), then you don’t return the correct answer, and in fact you try to get the first and last character of the empty string, which will cause an exception.