Получить длину списка в Python, используя рекурсию

Я пытаюсь рассчитать длину списка. Когда я запускаю его на cmd, я получаю:

RuntimeError: максимальная глубина рекурсии превышена по сравнению

Я не думаю, что что-то не так с моим кодом:

def len_recursive(list):
    if list == []:
        return 0
    else:
        return 1 + len_recursive(list[1:])
Источник

6 ответов

Решение

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

def len_recursive(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return loop(lst[1:], acc + 1)
    return loop(lst, 0)

Но в действительности вам придется использовать более короткие списки и / или увеличивать максимально допустимую глубину рекурсии.

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

Источник

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

Если вы настаиваете на рекурсии, эффективный способ:

def len_recursive(lst):
    if not lst:
        return 0
    return 1 + len_recursive(lst[1::2]) + len_recursive(lst[2::2])
Источник

Как объяснили другие, есть две проблемы с вашей функцией:

  1. Это не хвостовая рекурсия, поэтому он может обрабатывать только списки, пока sys.getrecursionlimit,
  2. Даже если бы это была хвостовая рекурсия, Python не выполняет оптимизацию хвостовой рекурсии.

Первое легко решить. Например, см. Ответ Оскара Лопеса.

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

Начните с Пола Батлера tail_rec функция:

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return (lambda x: tail(fun(x)))

Это не работает как декоратор для его случая, потому что у него есть две взаимно-рекурсивные функции. Но в вашем случае это не проблема. Итак, используя версию Оскара Лопеса:

@tail_rec
def tail_len(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return lambda: loop(lst[1:], acc + 1)
    return lambda: loop(lst, 0)

И сейчас:

>>> print tail_len(range(10000))
10000

Тад.

Если вы действительно хотите использовать это, вы можете сделать tail_rec в лучший декоратор:

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return functools.update_wrapper(lambda x: tail(fun(x)), fun)
Источник

Представьте, что вы используете это, используя стопку бумаги. Вы хотите посчитать, сколько листов у вас есть. Если кто-то дает вам 10 листов, возьмите первый лист, положите его на стол и возьмите следующий лист, поместив его рядом с первым листом. Вы делаете это 10 раз, и ваш стол довольно полон, но вы изложили каждый лист. Затем вы начинаете считать каждую страницу, перерабатывая ее по мере подсчета, 0 + 1 + 1 + ... => 10. Это не лучший способ подсчета страниц, но он отражает рекурсивный подход и реализацию Python.

Это работает для небольшого количества страниц. Теперь представьте, что кто-то дает вам 10000 листов. Довольно скоро на вашем столе нет места для размещения каждой страницы. По сути, это то, о чем говорится в сообщении об ошибке.

Максимальная глубина рекурсии - это "сколько листов" может хранить таблица. Каждый раз, когда вы вызываете python, необходимо хранить "1 + результат рекурсивного вызова", чтобы после того, как все страницы были разложены, он мог вернуться и подсчитать их. К сожалению, вам не хватает места до окончательного подсчета.

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

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

Источник

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

def len_iterative(lst):
    length = 0
    while lst:
        length += 1
        lst = lst[1:]
    return length

Обратите внимание, что это, вероятно, все еще будет ужасным решением, так как lst[1:] будет продолжать создавать копии списка. Таким образом, вы в конечном итоге len(lst) + 1 список экземпляров (с длинами 0 в len(lst)). Это, вероятно, лучшая идея, чтобы просто использовать встроенный len напрямую, но, думаю, это было задание.

Источник

Python не оптимизирует вызовы хвостовой рекурсии, поэтому использование таких рекурсивных алгоритмов не является хорошей идеей. Вы можете настроить стек с помощью sys.setrecursionlimit (), но это все же не очень хорошая идея.

Источник
Другие вопросы по тегам