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

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

Мне задали решить задачу. Я написал код, но он работает медленно. Мне нужно ускорить рекурсию. Если 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) 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итерацию можно назвать противоположностью рекурсии. Всегда, когда задачу можно решить итерацией (либо итерацией с использованием стека), следует делать выбор в пользу цикла 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

Увеличьте свой код в миллион раз | Рекурсия | Алгоритмы

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

Функция использует рекурсию, чтобы проверить, является ли слово палиндромом, вызывая себя несколько раз с разными параметрами.

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

Рекурсию можно использовать для обхода древовидной структуры, независимо от типа узлов, путем перебора дочерних узлов в цикле до тех пор, пока в дочернем массиве больше не останется элементов.

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

Рекурсивная функция в видео разбивает последовательность, уменьшая число на одну или две единицы, пока оно не достигнет базового значения 0 или 1.

Рекурсия допускает повторение функции внутри самой себя, что приводит к более эффективному и лаконичному коду.

Рекурсия в оптимизации алгоритма

️ Оптимизация кода с использованием рекурсии может значительно ускорить время выполнения, что значительно ускоряет решение проблем.

Кэшируя результаты каждого вычисления, динамическое программирование уменьшает необходимость обхода всех узлов дерева, что приводит к ускорению вычислений.

Использование рекурсии и кэширования может значительно ускорить процесс вычислений в алгоритмах.

Благодаря оптимизации алгоритма последовательность Фибоначчи может быть вычислена практически мгновенно для больших чисел без необходимости кэширования.

Summarize any video by yourself