-1

При выполнении сложных учебных задач (например, на алгоритмы или структуры данных) у многих (и у меня) периодически возникают проблемы из-за использования рекурсии. Либо превышается допустимый размер стека, либо программа выполняется дольше, чем допустимо по условию. В реальной работе это будет означать медленную работу программы либо неэффективное использование ресурсов компьютера.

При этом не очень легко найти поиском простые способы ухода от таких проблем, статьи чаще о сложных случаях, приходится придумывать, а при отсутствии навыка это может быть не быстро. Здесь предлагается поместить небольшую коллекцию простых методов (идеально, если читающие добавят их сами в виде ответов). Лучше с фокусом на Python, но принципиально большинство должно по логике подходить для многих языков программирования. Полагаю, сообществу должно быть полезно иметь это в базе знаний.

7
  • 2
    Если рекурсивную функцию удалось переписать в форму хвостовой рекурсии, то переход к циклу делается автоматически. Если функция сложная, то можно сделать итерацию с использованием массива в качестве стека. Если всё ещё сложнее, можно построить дерево вызовов, которое обрабатывается итеративно. 6 июл 2022 в 16:00
  • "папа, а ты с кем разговариваешь?":-) И что значит "автоматически" - это значит "просто" или это значит, что компилятор сам переведет? 6 июл 2022 в 16:02
  • "автоматически" - (не сложно) делается руками программиста, знакомого с инструкцией. 6 июл 2022 в 16:04
  • Так все простые методы делаются "автоматически". Просто мне в час ночи подумать все же пришлось минут 15. Вот и записал результат размышлений ("мама, я открыл второй закон Ньютона!":-)). 6 июл 2022 в 16:05

1 ответ 1

0

Вот несколько самых простых способов на Python (скорее всего, легко портируются и для других языков).

Все их реально применил при решении мной вчера задачи на Stepik (там более сложные примеры, конечно, были, тут упростил для понимания читающих), да и в других случаях применял:

1) При проблеме с допустимой глубиной рекурсии, если не избавляться от самой рекурсии:*

надо добавить в код строку sys.setrecursionlimit (50000) - параметр в скобках с таким большим значением во всех моих случаях решал вопрос (по умолчанию этот параметр равен 1000 или чуть менее, в первом примере ниже ошибка появится при a = 998). Требуется ещё import sys,конечно.

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

*встречавшиеся мне ошибки при превышении глубины рекурсии:

RecursionError: maximum recursion depth exceeded in comparison и

RecursionError: maximum recursion depth exceeded while calling a Python object

2) При рекурсивном вызове в конце функции:

def test (a):
    a -= 1
    if a > 0:
        print (a)
    else:
        return
    test(a)


if __name__ == '__main__':
    a = 997
    test (a)

переделать функцию можем просто с помощью while True, уйдя от рекурсии:

def test (a):
    while True:
        a -= 1
        if a > 0:
            print (a)
        else:
            return

3) При варианте чуть сложнее с рекурсивными вызовами в середине функции:

def test(a, b):
    print ('test start, a, b', a, b)
    if a > 5:
        print('condition a')
        return test(a-1, b)
    if b < 5:
        print('condition b')
        return test(a, b+1)
    print ('test finish, a, b', a, b)


if __name__ == '__main__':
   a = 7
   b = 3

надо еще добавить continue и break, чтобы уйти от рекурсии, помимо while True:

def test(a, b):
    while True:
        print ('test start, a, b', a, b)
        if a > 5:
            print('condition a')
            a -= 1 
            continue
        if b < 5:
            print('condition b')
            b += 1
            continue
        print('test finish, a, b', a, b)
        break
1
  • Комментарии не предназначены для расширенной дискуссии; разговор перемещён в чат.
    – Grundy
    6 июл 2022 в 18:15

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.