Как ускорить рекурсию в с

Действительно ли всякое рекурсивное вычисление можно заменить на нерекурсивное?

Рекурсия выразительна. Код сложных алгоритмов с применением рекурсии выходит компактнее и естественнее, чем с применением итерации.

Ответ написан более двух лет назад

Комментировать

Нравится 1 Комментировать

Ваш ответ на вопрос

Войдите, чтобы написать ответ

• Python
• +1 ещё

Не понимаю, почему программа «тяжелая»?

• 1 подписчик
• вчера
• 161 просмотр

Один чувак на StackOverlow сказал: «Циклы могут ускорить работу программы, рекурсия может ускорить работу программиста».

Это зависит от способа мышления. Мне, например, не нравится рекурсия. Мне проще писать функцию в линейном ключе, последовательно её усложняя.

Остальные ответы
а рекурсия с мемоизацией помогает программисту минимизировать эту разницу
Παν μέτρον άριστονМыслитель (9566) 4 года назад

Рекурсия — зло. Она пойдет только как общеразвивающая практика при обучении. То, что с её помощью быстрее, это не факт. Кто сказал, что написать в три раза больше более понятного кода медленнее, чем в три раза меньше менее понятного кода?

DONER KEBAB Просветленный (34259) есть случаи, когда код с рекурсией + мемоизацией практически необходим, например просчет факториала с матрицей, причем если это писать на компилируемом языке, то качественный компилятор может убрать вызовы функции в принципе, а код останется в разы короче и понятнее дело не в рекурсии, а где ее применять, на пустом месте вызывать функции, которые даже в c++ по 50мкс могут быть это неправильный подход

Любую рекурсию можно преобразовать в цикл с использованием дополнительной очереди LIFO (стек). Любой цикл можно записать в виде рекурсии. Хвостовая рекурсия элементарно преобразуется в простой цикл без стека и многие компиляторы умеют это делать автоматически.

Производительность программиста зависит от его квалификации и конкретной задачи, а не от использования циклов / рекурсии. Рекурсия может как упростить код, так и усложнить его. И это сильно зависит от языка программирования. Например, алгоритм Евклида в Pascal или C проще записать рекурсией, а в Python или Go — циклом.

NextМудрец (19655) 4 года назад

Если компилятор не преобразует рекурсию в цикл, то рекурсия должна медленней работать и и больше стэка сожрать, нет?

Андрей Высший разум (392433) Совершенно верно. Но переделывая вручную рекурсивный алгоритм в циклический, можно наворотить такого, что скорость и потребление памяти окажутся хуже, чем для исходной рекурсии.

Один из методов оптимизации — разворачивание циклов. При каждом условном переходе сбивается конвейер.

а зачем ускорение программы щас вообще ?
АндрейВысший разум (392433) 4 года назад
На Arduino, в IoT и т. д. очень даже актуально. Это только на PC «железо всё вытянет».

Максимильян Тигр Профи (899) я рад что хотя бы про компьютеры я оказался прав, конечно есть кучу мест где скорость имеет значение, но я предполагаю что это обычный программист)

Мне нужно ускорить рекурсию

Мне задали решить задачу. Я написал код, но он работает медленно. Мне нужно ускорить рекурсию. Если n будет равен даже 70 расчеты займет очень много времени. Помогите мне улучшить мой код. Максимальное n может быть 500!

def a(n): if n == 1: return 1 if n == 2: return 2 return 1 + a(n - a(a(n - 1))) 

Отслеживать
задан 29 окт 2020 в 19:01
130 15 15 бронзовых знаков
вы бы еще сказали что эта рекурсия делает, может можно было бы обойтись и без рекурсии
29 окт 2020 в 19:05

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

дело в том, что функция a(n) вызывается многократно, а значит рекурсий больше, чем нужно

можно вычислить a(n) однократно и дальше только использовать уже вычисленные значения

res = [0 for _ in range(1000)] def a(n): if res[n] == 0: if n > 2: res[n] = 1 + a(n - a(a(n - 1))) elif n == 1: res[n] = 1 elif n == 2: res[n] = 2 return res[n] print(a(900)) 

a(900) работает мгновенно, так что можно считать это оптимизацией 🙂

только учтите одну важную вещь, я не знаю как у питона, но при рекурсии у того же c++ вызовы запихиваются в стек и стек может просто переполниться

в моем примере при n = 1000 питон уже ругается

RecursionError: maximum recursion depth exceeded in comparison 

P.S.

в коде много if, поэтому лучше сделать ее покороче

res = [0, 1, 2] + [0 for _ in range(10)] def a(n): if res[n] == 0: res[n] = 1 + a(n - a(a(n - 1))) return res[n] print(a(10)) 

да и вообще зачем нам эти if?

res = [0, 1, 2] + [0 for _ in range(20)] def a(n): res[n] = res[n] or (1 + a(n - a(a(n - 1)))) return res[n] print(res) 

Как ускорить рекурсию в с

Итерацию можно назвать противоположностью рекурсии. Всегда, когда задачу можно решить итерацией (либо итерацией с использованием стека), следует делать выбор в пользу цикла for или while вместо рекурсии.

Мемоизация

Если применение рекурсии при решении задачи неизбежно, есть простой способ ускорить выполнение функции – для этого используют декоратор @lru_cache() модуля functools. Сравним скорость выполнения рекурсивного кода при решении следующей олимпиадной задачи.

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

В решении используется рекурсивная функция, выполнение которой в интерпретаторе Python занимает столько времени, что готовое решение никогда не будет соответствовать строгим олимпиадным критериям. Для кэширования промежуточных результатов можно написать функцию мемоизации самостоятельно, а можно воспользоваться готовым, уже упомянутым выше декоратором. Сравним скорость выполнения решений с мемоизацией и без:

Пример ввода:

Посещаем узел Анна. Проверяем, состоит ли имя Анна из 9 букв. Посещаем узел Егор. Проверяем, состоит ли имя Егор из 9 букв. Посещаем узел Мария. Проверяем, состоит ли имя Мария из 9 букв. Посещаем узел Светлана. Проверяем, состоит ли имя Светлана из 9 букв. Посещаем узел Инга. Проверяем, состоит ли имя Инга из 9 букв. Посещаем узел Елизавета. Проверяем, состоит ли имя Елизавета из 9 букв. Имя из 9 букв: Елизавета 

root = ]>, , ]>, ]>]> def find_name(node): print(f"Посещаем узел . ") print(f"Проверяем, состоит ли имя из 9 букв. ") if len(node['name']) == 9: return node['name'] # граничный случай if len(node['children']) > 0: # рекурсивный случай for child in node['children']: returnValue = find_name(child) if returnValue != 'не найдено': return returnValue return 'не найдено' # граничный случай - имен из 9 букв нет print(f"Имя из 9 букв: ") 

Примечание: без рекурсии такую задачу можно решить с помощью ООП:

class Node: def __init__(self, data=None, left=None, right=None): self.data = data self.left = left self.right = right def traverse(root): if root is None: return traverse(root.left) if len(root.data) == 9: print(f'Имя найдено: ') return traverse(root.right) if len(root.data) == 9: print(f'Имя найдено: ') return if __name__ == '__main__': root = Node('Анна') root.left = Node('Егор') root.right = Node('Светлана') root.left.left = Node('Мария') root.right.left = Node('Инга') root.right.right = Node('Марина') root.right.left.left = Node('Елизавета') root.right.left.right = Node('Антон') traverse(root) 

Задание 9

Имеется многомерный вложенный список:

sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] 

Напишите рекурсивную и итеративную функции для преобразования списка в одномерный.

Ожидаемый результат:

[5, 7, 2, 4, 9, 5, 2, 5, 4, 3, 2, 1, 5, 9, 5, 4, 3, 1, 2, 4, 7, 2, 6, 4, 4, 1, 6, 3, 8, 4, 5, 9, 1, 3, 1, 5, 6, 4, 2, 1, 2, 5, 6, 8, 2, 3, 4, 5, 3, 2, 2, 1, 4, 2, 5, 4, 3, 1, 6, 7, 9, 0, 5, 2, 4, 7, 3, 4, 4, 2, 5, 6, 7, 5, 7, 1, 3, 4, 6, 6, 4, 5] 

Решение 1 – рекурсивное:

def flat_list_recur(lst): if lst == []: return lst if isinstance(lst[0], list): return flat_list_recur(lst[0]) + flat_list_recur(lst[1:]) return lst[:1] + flat_list_recur(lst[1:]) sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_recur(sp)) 

Решение 2 – итеративное:

def flat_list_iter(lst): result = [] stack = [lst] while stack: current = stack.pop(-1) if isinstance(current, list): stack.extend(current) else: result.append(current) result.reverse() return result sp = [[[5, 7, 2], [4, 9, 5]], [[2, 5, 4]], [[3, 2, 1], [[5], [9, 5]]], [4, 3, 1, 2], [[4, 7, 2], [6, 4]], [[[4, 1, 6], [3, 8]], [4, 5]], [9, 1], [3, 1], [[5, 6], [[4, 2, 1], [2, 5], [[6, 8, 2, 3, 4]]]], [5, 3, 2], [2, [1], 4], [2, 5, [4, 3, 1], 6, 7, [9, 0, 5, 2, 4]], [7, 3, [4]], [4, 2, [[[5, 6, 7], 5, 7]], 1], [3, 4, 6, [6, 4, 5]], ] print(flat_list_iter(sp)) 

Задание 10

Реализуйте алгоритм бинарного поиска с помощью итеративной и рекурсивной функций. Число задается с помощью randrange(2000), в списке хранятся числа от 1 до 1000, т.е. не во всех случаях заданное число будет присутствовать в списке.

Пример вывода:

Число найдено: 787 

Решение 1 – рекурсивное:

from random import randrange def binary_recursive(lst, start, end, num): if end >= start: mid = (end + start) // 2 if lst[mid] == num: # граничный случай - элемент находится посередине return mid elif lst[mid] > num: # рекурсивный случай - элемент находится слева return binary_recursive(lst, start, mid - 1, num) else: # рекурсивный случай - элемент находится справа return binary_recursive(lst, mid + 1, end, num) else: # граничный случай - элемент в списке не обнаружен return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_recursive(sp, 0, len(sp)-1, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 

Решение 2 – итеративное:

from random import randrange def binary_iter(lst, num): start, end, mid = 0, len(lst) - 1, 0 while start num: end = mid - 1 else: return mid return 'не найдено' sp = [i for i in range(1001)] n = randrange(2000) result = binary_iter(sp, n) if result != 'не найдено': print(f'Число найдено: ') else: print('Такого числа нет в списке') 

Подведем итоги

Рекурсию стоит применять для решения задач, в которых:

• Используется древовидная структура данных.
• Нужно предусмотреть возврат к предыдущей отправной точке (например, при поиске выхода из лабиринта).
• Глубина рекурсивных вызовов находится в пределах разумного и не приведет к переполнению стека.

Во всех остальных случаях целесообразнее использовать итерацию либо итерацию и стек.

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

1. Особенности, сферы применения, установка, онлайн IDE
2. Все, что нужно для изучения Python с нуля – книги, сайты, каналы и курсы
3. Типы данных: преобразование и базовые операции
4. Методы работы со строками
5. Методы работы со списками и списковыми включениями
6. Методы работы со словарями и генераторами словарей
7. Методы работы с кортежами
8. Методы работы со множествами
9. Особенности цикла for
10. Условный цикл while
11. Функции с позиционными и именованными аргументами
12. Анонимные функции
13. Рекурсивные функции
14. Функции высшего порядка, замыкания и декораторы
15. Методы работы с файлами и файловой системой
16. Регулярные выражения
17. Основы скрапинга и парсинга
18. Основы ООП: инкапсуляция и наследование
19. Основы ООП – абстракция и полиморфизм
20. Графический интерфейс на Tkinter
21. Основы разработки игр на Pygame
22. Основы работы с SQLite
23. Основы веб-разработки на Flask
24. Основы работы с NumPy
25. Основы анализа данных с Pandas