рекурсия со списком в python

Question

Я только начал изучать Python, и есть некоторые рекурсивные вопросы, которые я не могу понять. Наиболее раздражающим является следующее: мне нужно построить функцию ind(e,L), где e - это целое число, а L - это список.

Путем ввода e, если оно есть в списке, выводдолжен быть его индекс Например:

ind(42,[0,14,52,42,15]) -> 3

Это код, который я написал до сих пор, но индекс, который я получаю, всегда равен 0. Может кто-нибудь объяснить мне, что я делаю неправильно?

def location(e,L):
    if L == []:
        return False
    elif e == L[0]:
        A = L[:-1].index(e)
        return A
    else:
        return location(e,L[1:])

print(location(14,[1,2,14,1]))

спасибо:)

Answer 1

Вы возвращаете, только если e имеет индекс 0 (вы можете пропустить термин L[:-1]..., он всегда равен 0) и распространять его без изменений. Вместо того, чтобы возвращать бессмысленный индекс, верните количество рекурсий. Самый простой способ - добавить 1 всякий раз, когда функция повторяется.

def location(element, sequence):
    if not sequence:
        # e is not in the list at all
        # it is not meaningful to return an index
        raise IndexError
    elif element == sequence[0]:
        # we already know where e is
        # since we checked it explicitly
        return 0
    else:
        # keep searching in the remainder,
        # but increment recursion level by 1
        return 1 + location(element, sequence[1:])

Answer 2

Я тоже новичок, но я думаю, что это должно сработать ...

def function(e,L):
    try:
        x = 0
        for val in L:
            if e == val:
                return(x)
            else: x = x+1
    except:
        print('List provided does not contain any values')

x будет считать значения и возвращать, когда индекс равен значению в списке. Он также вернет несколько совпадений, что может быть полезно.

Answer 3

Короче рекурсивное решение:

def ind(a, b):
   def _ind(a, b):
     return False if not b else (b[0] == a or 1+_ind(a, b[1:]))
   return _ind(a, b) - 1

print(ind(42,[0,14,52,42,15]))

Вывод:

3

Если вы не возражаете против смещения на единицу:

def ind(a, b):
  return False if not b else (b[0] == a or 1+ind(a, b[1:]))

>>>ind(42,[0,14,52,42,15]) - 1

Или, используя значение по умолчаниюпараметр:

def ind(a, b, c = 0):
   return False if not b else (c if b[0] == a else ind(a, b[1:], c+1))

>>>ind(42,[0,14,52,42,15])

Answer 4

Мое решение немного другое. Я начинаю искать e с правого конца L. Если найден, то индекс просто равен длине L минус 1 (поскольку индексы Python начинаются с 0).

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

def location(e, L):
    if L:
        if L[-1] == e:
            return len(L)-1
        else:
            return location(e, L[:-1])
    return False

Тест:

>>> L = [0,14,52,42,15]
>>> location(42, L)
3

Answer 5

Следует отметить, что the time complexity и the space complexity вашего кода - O(n^2). Потому что L[1:] создает new list каждый раз! Это O(n) операция в терминах time и space.

---

Один правильный Pythonic способ сделать это:

def location(e, L):
    n = len(L)

    def _location(start):
        if start == n:
            raise IndexError

        if L[start] == e:
            return start

        return _location(start + 1)

    return _location(0)

print(location(14, [1, 2, 14, 1]))

Вывод:

2

---

Сложность времени: O(n)

Сложность пространства: O(n) (из-за рекурсии.)