Рекурсия в Python
В программировании рекурсия является фундаментальным понятием. В большинстве собеседований по Python могут задать вопрос на эту тему. Независимо от того, являетесь ли вы программистом или специалистом по обработке данных, эту концепцию должен знать каждый. Рекурсивны не только алгоритмы поиска и сортировки, но и каждое собеседование по Python будет включать некоторые вопросы, основанные на рекурсии. Это делает рекурсию ключевой концепцией, которую нужно пересматривать перед любым собеседованием по программированию.
Здесь я попытаюсь объяснить рекурсию максимально простым способом, разделив рекурсию на шаги:
- Что такое рекурсия?
- Почему мы используем рекурсию?
- Рекурсия в Python.
- Примеры рекурсии.
Что такое рекурсия?
Рекурсия — это математическая концепция, которую мы также используем в программировании. Рекурсия — это процесс определения проблемы в терминах самой себя. Это простейшее определение рекурсии.
В программировании рекурсия — это процесс, в котором функция вызывает себя прямо или косвенно, а соответствующая функция вызывается как рекурсивная функция.
Итак, вывод заключается в том, что рекурсия определяет новую, используя саму себя.
Почему мы используем рекурсию?
Большинство проблем решаются без рекурсии. Так что, строго говоря, в рекурсии обычно нет необходимости. Рекурсия предназначена для решения проблем, которые можно разбить на более мелкие повторяющиеся проблемы. Она особенно хороша для работы с вещами, которые имеют много возможных ветвей и слишком сложны для итеративного подхода.
- Быстрее при оптимизации.
- Меньше кода. Вы можете писать рекурсивный код быстрее, а для отладки у вас меньше кода для сравнения, чем итеративный код.
- Декларативная.
- Эффективная сортировка и поиск
- Максимальная глубина рекурсии.
- По ошибке или непреднамеренно использовать рекурсию без базового условия.
- Больше потребления памяти.
Рекурсия в Python
Когда вы вызываете функцию в Python, интерпретатор создает новое локальное пространство имен, чтобы имена, определенные в этой функции, не конфликтовали с идентичными именами, определенными в другом месте.
def recurse(): x = 5 recurse() Когда функция recurse() выполняется в первый раз, она создаст локальное пространство имен в python, а переменной x присваивается 10. После этого рекурсия () вызывает себя рекурсивно. При повторном выполнении рекурсии () интерпретатор создает второе пространство имен и также назначает переменной x значние 10. Эти два экземпляра имени x отличаются друг от друга и могут сосуществовать без конфликтов, поскольку они находятся в разных пространствах имен.
После выполнения рекурсии () она будет вызывать себя снова и снова, но python будет отображать трассировку, потому что невозможно запускать ее вечно.
RecursionError: maximum recursion depth exceededПотому что существует ограничение на рекурсию в соответствии с вашей системой.
Теоретически она будет работать вечно, но практически ничто не может быть вечным из-за ограничений памяти. Python не позволяет этому случиться. Интерпретатор ограничивает максимальное количество раз, которое функция может вызывать саму себя рекурсивно, и при достижении этого предела вызывает исключение RecursionError .
Итак, чтобы наша функция не запускалась навсегда, должно быть базовое условие.
Базовый вариант.
Базовое условие поможет завершить процесс рекурсии или остановить функцию, вызывая себя снова и снова. Есть один или несколько базовых случаев, которые решаются напрямую без необходимости дальнейшей рекурсии.
Рекурсивный случай.
Если желаемое состояние не было достигнуто, и функция переходит на другой рекурсивный шаг. Каждый рекурсивный вызов постепенно приближает решение к базовому случаю.
Примеры рекурсии
Обратный отсчет до нуля
def countdown(n): print(n) if n==0: return # Base condition. it will return None. else: return countdown(n-1) # Recursive call countdown(int(input('Enter number')))В приведенном выше примере пользователю будет предложено ввести номер. В базовом случае n = 0 и на этом рекурсия остановится. В рекурсивном случае в качестве аргумента n передается значение на единицу меньше, чем текущее значение, и, как и в этом случае, рекурсия приближается к базовому случаю.
Рассчет факториала
В следующем примере используется математическая концепция факториала. Факториал натурального числа n, обозначаемый как n! и рассчитывается как:
n! = n*(n-1)*(n-2). 3*2*1 Другими словами, n! является произведением всех целых чисел от 1 до n включительно.
def factorial(n): if nПримеров рекурсии может быть так много, но возникает вопрос: "Действительно ли это необходимо для реализации рекурсии?". Потому что эти два вышеперечисленных кода также можно записать с помощью цикла for. Второе - это скорость выполнения. Между рекурсивными и нерекурсивными решениями (итеративными) могут быть значительные различия в производительности.
Это был один из немногих простых примеров рекурсии.
Я перечисляю некоторые из примеров, на которых вы можете попрактиковаться или изучить рекурсию, чтобы получить опыт. Я не объясняю эти примеры, потому что, возможно, любой новичок прочтет эту статью, а затем он или она запутается, когда увидит эти предварительные примеры рекурсии в структуре данных. Чтобы упростить эту статью, я просто пишу названия примеров.
Источник:
Как остановить рекурсию?
Создаю модуль на Python по нахождению указанного типа файла (.jpg, .dll, .mp4) в указанной директории. Мой код:
import os import sys import time time.sleep(0.3) def walker(directory, access): for name in os.listdir(directory): path = os.path.join(directory, name) check = os.path.basename(path) if os.path.isfile(path): if check[len(check)-4:] == access: print('[found] ' + str(access) + ' file ' + path) else: walker(path, access) if __name__ == '__main__': walker('C:\\Users\Admin\Desktop', '.455')
Проблема в том, что из за рекурсии не могу просчитать сценарий, когда введенного расширения и файла не существует в директории, этот сценарий выводится многочисленно( к примеру not found выводится очень много раз), а нужно всего лишь единично. Как мне исправить данный дефект?
Отслеживать
задан 29 июн 2019 в 18:41
PythonLearner4823 PythonLearner4823
101 1 1 золотой знак 2 2 серебряных знака 9 9 бронзовых знаков
В вашем примере нигде не выводится " not found ". К тому же, рекурсия конечна и ошибок в ней нет.
29 июн 2019 в 18:58
Не подскажите, как мне реализовать вывод Not found без зацикливания?
29 июн 2019 в 19:01
Задача написать именно свой модуль? А то можно однострочником pathlib.Path(directory).rglob('*' + access)
30 июн 2019 в 11:38
Да, я чисто свой модуль писал. Для практики)
1 июл 2019 в 15:39
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Для того, чтобы определить пустоту какой-либо папки, я решил возвращать True , если в ней найден файл с нужным расширением.
Таким образом, если функция возвращает None , мы можем гарантировать, что все подпапки, которые она парсила, тоже пусты, после чего сделать соответствующий вывод.
import os def walker(dir, ext): for name in os.listdir(dir): path = os.path.join(dir, name) if os.path.isfile(path): f_name, f_ext = os.path.splitext(path) if f_ext == ext: print(f'[found] : ') return True else: if not walker(path, ext): print(f'[not found] in ') if __name__ == '__main__': walker(r'C:\Users\Username\Desktop', '.txt') - Исправил ошибку, связанную с проверкой расширения (Ваш код проверяет расширение только из 3 символов)
- Использовал формат-строки для упрощения вывода
- Использовал сырую строку для упрощения передачи директории в функцию
- Удалил неиспользуемые модули из импорта
- Удалил неиспользуемые переменные
- Расставил отступы и абзацы для улучшения читабельности кода
Отслеживать
ответ дан 29 июн 2019 в 19:51
18.4k 5 5 золотых знаков 24 24 серебряных знака 48 48 бронзовых знаков
Большое спасибо за помощь! Вызывает вопрос строка f_name, f_ext = os.path.splitext(path) . Я так понял, f_ext - это строка с расширением, ничего не путаю?) И еще вопрос к буковке f в начале функции print() . Зачем Вы ее использовали и на что она влияет?)
1 июл 2019 в 15:51
@PythonLearner4823 Про f_ext Вы всё правильно поняли - это расширение файла. Оно может быть разной длины, поэтому я решил использовать специальную функцию для этого. А конструкция f'' - это формат-строка. Она появилась в Python 3.6 и позволяет очень удобно форматировать строки. Вместо конструкции
1 июл 2019 в 15:56
Ага, понятно. Еще вопросик к строке if not walker(path, ext): . Я так понимаю, этот оператор выполняется, если предыдущий не вернул True , верно? И разве после return True цикл не должен останавливаться?
1 июл 2019 в 16:02
@PythonLearner4823 Да, это условие выполняется, если функция walker вернёт None (так происходит, если вообще не указать return , или указать без возвращаемых данных). Это происходит потому что логический оператор not инверсирует логический тип. (простыми словами, меняет ложь на истину, а истину на ложь). В Вашем случае not None - это истина.
1 июл 2019 в 16:06
То есть if not walker(path, ext) эквивалентен if True: ?
1 июл 2019 в 16:07
Ответ от @nomnoms12 довольно хорош, но не избавил от проблемы вывода огромного числа числа not found . Решить это можно несколькими способами.
Вариант 1. Использовать отдельную рекурсивную функцию, а вывод оставить в не-рекурсивной:
import os def walker(dir, ext): def recursive(dir): for name in os.listdir(dir): path = os.path.join(dir, name) if os.path.isfile(path): f_name, f_ext = os.path.splitext(path) found = f_ext == ext else: found = recursive(path) if found: return True return False if recursive(dir): print(f'[found] : ') else: print(f'[not found] in ') if __name__ == '__main__': walker(r'/Users/aivanf/Desktop', '.txt') Того же самого результата можно добиться используя одну функцию с аргументом, который будет отвечать за надобность вывода текста, у которого значение по умолчанию выводит текст, а в рекурсивных вызовах не выводит. Но это не очень красиво.
Обратите внимание, переменная ext во вложенную функцию передаётся из контекста внешней функции.
Также стоит отметить, что при рекурсивной реализации получается поиск в глубину. То есть, если нужный файл лежит в указанной директории, но среди контента это директории он в конце, то сначала будут перебираться все вложенные папки и их содержимое.
Вариант 2. Обойдёмся без рекурсии используя простой список. Здесь можно легко реализовать как поиск в ширину, так и в глубину. Если искомый файл лежит непосредственно в данной директории, то такой поиск будет быстрее.
import os def walker(dir, ext): paths = [dir] found = False while paths: current = paths.pop(0) for name in os.listdir(current): path = os.path.join(current, name) if os.path.isfile(path): f_name, f_ext = os.path.splitext(path) if f_ext == ext: print(f'[found] in ') return True else: # Новые папки добавляем в конец списка, # то есть, рассмотрим их после всех файлов. paths.append(path) # Это поиск в ширину # Для поиска в глубину надо просто заменить на `insert` print(f'[not found] in ') return False if __name__ == '__main__': walker(r'/Users/aivanf/Desktop', '.txt') Устранение рекурсии в Python
Привет, Хабр! Представляю вашему вниманию перевод статьи "Removing a recursion in Python, part 1" автора Эрика Липперта (Eric Lippert).
На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.
В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.
Недавний вопрос на StackOverflow заставил меня задуматься, как преобразовать рекурсивный алгоритм в итеративный, и оказалось, что Python довольно подходящий язык для этого.
Проблема с которой столкнулся автор вопроса заключалась в следующем:
- Игрок находится в произвольной клетке на пронумерованном поле;
- Цель вернуться в клетку №1;
- Если игрок находится на чётной клетке, он платит одну монету и проходит половину пути к клетке №1;
- Если игрок находится на нечётной клетке, он может заплатить 5 монет и сразу перейти на первую клетку или заплатить одну монету и сделать один шаг к клетке №1 — на чётную клетку.
Вопрос заключается в следующем: какое наименьшее количество монет необходимо заплатить, чтобы вернуться из текущей клетки в первую.
Задача имеет очевидное рекурсивное решение:
def cost(s): if s Однако эта программа падала, достигая максимальной глубины рекурсии, вероятнее всего из-за того, что автор вопроса экспериментировал с очень большими числами.
Следовательно возникает вопрос: как превратить рекурсивный алгоритм в итерационный на Python?
Перед тем как мы начнем, хочу отметить, что конечно существуют более быстрые решения этой конкретной задачи, сама по себе она не очень интересна.
Скорее эта задача послужила лишь отправной точкой в вопросе, как в общем случае избавиться от единственного рекурсивного вызова в программе на Python.
Смысл в том, что можно преобразовать любой простой рекурсивный метод и избавиться от рекурсии, а это всего лишь пример, который оказался под рукой.
Техника, которую я собираюсь показать, конечно не совсем соответствует тому, как принято писать на Python, вероятно решение в Python-стиле использовало бы генераторы или другие возможности языка.
Что я хочу показать здесь, так это как избавиться от рекурсии, используя последовательность маленьких и безопасных преобразований, приводящих функцию к такой форме, в которой легко произвести замену рекурсии на итерацию.
Для начала давайте посмотрим как привести программу к такой форме.
На первом шаге нашего преобразования я хочу чтобы вычисления производимые до рекурсивного вызова сводились к вычислению аргумента, а вычисления, после рекурсивного вызова, производились в отдельном методе, который принимает результат рекурсивного вызова.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s Вторым шагом я хочу вынести вычисление аргумента в отдельную функцию:
# . def get_argument(s): if s % 2 == 0: return s // 2 return s - 1 def cost(s): if s На третьем шаге, я хочу добавить вспомогательную функцию, которая будет выбирать функцию-продолжение, вызываемую после возврата из рекурсии.
Обратите внимание, что вспомогательная функция возвращает функцию.
#. def get_after(s): if s % 2 == 0: return add_one return get_min def cost(s): if s Теперь запишем это в более общей и краткой форме:
#. def is_base_case(s): return s Видно, что каждое проделанное изменение сохраняло смысл программы.
Сейчас проверка на чётность числа выполняется дважды, хотя до изменений проверка была одна.
Если мы захотим, то можем решить эту проблему объединив две вспомогательные функции в одну, возвращающую кортеж.
Но давайте не будем беспокоиться об этом в рамках решения этой задачи.
Мы свели наш рекурсивный метод до максимально общей формы.
- В базовом случае:
- вычисляем значение, которое нужно вернуть;
- возвращаем его.
- вычисляем аргумент рекурсии;
- производим рекурсивный вызов;
- вычисляем возвращаемое значение;
- возвращаем его.
Кое-что важное на что необходимо обратить внимание на этом шаге — это то, что after не должен сам содержать вызовов cost .
Способ, который я показываю здесь, удаляет единственный рекурсивный вызов.
Если у вас 2 и более рекурсии, то нам понадобится другое решение.
Как только мы привели наш рекурсивный алгоритм к такой форме, преобразовать его в итеративный уже просто.
Хитрость в том, чтобы представить, что происходит в рекурсивной программе.
Как мы делаем рекурсивный спуск: мы вызываем get_argument перед рекурсивным вызовом и вызываем функцию after после возврата из рекурсии.
То есть, все вызовы get_argument происходят перед всеми вызовами after.
Поэтому мы можем преобразовать это в 2 цикла: первый вызывает get_argument и формирует список функций after, а второй вызывает все функции after:#. def cost(s): # Создаём стек из функций "after". Все эти функции # принимают результат рекурсивного вызова и возвращают # значение, которое вычисляет рекурсивный метод. afters = [ ] while not is_base_case(s): argument = get_argument(s) after = get_after(s) afters.append(after) s = argument # Теперь у нас есть стек функций "after" : result = base_case_value(s) while len(afters) != 0: after = afters.pop() result = after(result) return resultБольше никакой рекурсии!
Выглядит как магия, но все что мы здесь делаем — то же самое, что делала рекурсивная версия программы и в том же порядке.
Этот пример отражает мысль, которую я часто повторяю о стеке вызовов: его цель сообщить то, что произойдёт дальше, а не то, что уже произошло!
Единственная полезная информация в стеке вызовов в рекурсивной версии программы — это какое значение имеет after, поскольку эта функция вызывается следующей, а все остальное на стеке не важно.
Вместо использования стека вызовов, как неэффективного и громоздкого способа хранения стека after, мы можем просто хранить стек функций after.
В следующий раз мы рассмотрим более сложный способ удаления рекурсии на Python.
Как остановить рекурсию python
Рекурсия - это мощный инструмент в программировании, который может быть использован для решения многих задач. В Python, рекурсия может быть использована для вычисления факториала, чисел Фибоначчи, обхода деревьев и многих других задач.
В программировании рекурсия является мощным инструментом, который может использоваться для решения многих задач. Давайте рассмотрим, как использовать рекурсию в Python и как она работает.
Основы рекурсии в Python
Рекурсивная функция должна иметь базовый случай (base case) и рекурсивный случай (recursive case). Базовый случай - это условие, в котором функция не вызывает саму себя, а возвращает значение. Рекурсивный случай - это условие, в котором функция вызывает саму себя.
Например, рекурсивная функция для вычисления факториала может выглядеть так:
# Рекурсивная функция для вычисления факториала числа def factorial(n): # Базовый случай - если n равно 0, то возвращается 1 if n == 0: return 1 # Рекурсивный случай - если n не равно 0, то вызывается функция factorial для n-1 и умножается на n else: return n * factorial(n-1)Описание функции factorial :
Рекурсивная функция factorial вычисляет факториал числа n . Факториал числа n - это произведение всех целых чисел от 1 до n , включительно. Например, факториал числа 5 равен 1 * 2 * 3 * 4 * 5, т.е. 120.
Функция factorial использует базовый случай n == 0 , чтобы остановить рекурсию. Если n равно 0, то возвращается 1 - это базовый случай. Если n не равно 0, то функция вызывает саму себя, передавая в качестве аргумента n-1 . Это рекурсивный случай. Рекурсия продолжается, пока n не станет равным 0.
Примеры использования рекурсии в Python
Рекурсия может быть использована для решения многих задач. Например, мы можем использовать рекурсию для вычисления чисел Фибоначчи. Числа Фибоначчи - это последовательность чисел, где каждое число равно сумме двух предыдущих чисел. Первые два числа равны 0 и 1. Таким образом, последовательность начинается так: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.
Рекурсивная функция для вычисления чисел Фибоначчи может выглядеть так:
def fibonacci(n): # Базовый случай - если n равно 0, то возвращается 0 if n == 0: return 0 # Базовый случай - если n равно 1, то возвращается 1 elif n == 1: return 1 # Рекурсивный случай - вызов функции fibonacci для n-1 и n-2 и возвращение их суммы else: return fibonacci(n-1) + fibonacci(n-2)Описание функции fibonacci :
Рекурсивная функция fibonacci вычисляет n-ое число Фибоначчи. Функция использует два базовых случая - когда n равно 0 и когда n равно 1 - для остановки рекурсии. В рекурсивном случае, функция вызывает саму себя для двух предыдущих чисел и возвращает их сумму.
Рекурсия также может быть использована для обхода деревьев. Дерево - это структура данных, которая состоит из узлов и связей между ними. Каждый узел имеет родителя и может иметь несколько дочерних узлов. Обход дерева - это процесс посещения каждого узла дерева ровно один раз.
Рекурсивная функция для обхода дерева может выглядеть так:
def traverse_tree(node): # Базовый случай - если узел равен None, то возвращается None if node is None: return # Рекурсивный случай - вызов функции traverse_tree для левого и правого поддерева traverse_tree(node.left) traverse_tree(node.right)Описание функции traverse_tree :
Рекурсивная функция traverse_tree обходит дерево, начиная с корневого узла. Функция использует базовый случай node is None , чтобы остановить рекурсию, когда дошли до конца поддерева. В противном случае, функция вызывает себя для левого и правого поддерева.
Заключение
Рекурсия - это один из способов решения задач в программировании. Хотя рекурсия может быть мощным инструментом, ее необходимо использовать с осторожностью и пониманием. Для использования рекурсии в Python необходимо понимать основные принципы рекурсии, а также уметь правильно выбирать базовый и рекурсивный случаи для каждой задачи.