Очень быстрый и простой вопрос о домашнем задании. У меня все работает нормально, но я думаю, что там лучше
способ сделать это. Более питоновский путь.
Здесь мой код рекурсивно уменьшает каждый элемент списка на 1.
l = range(30)
def recurseDecrMap(l, x = []):
if len(l) == 0:
return []
else:
x.append(l[0] -1)
recurseDecrMap(l[1:], x)
return x
Так спасибо за любой вход. Я пытаюсь научиться лучше рекурсии. Проблемы с получением умение его.
Вы можете использовать только один аргумент, на мой взгляд это проще:
def recurseDecrMap(l):
if not l:
return []
else:
return [l[0]-1] + recurseDecrMap(l[1:])
Но, как отметил @jamylak, сложность этого алгоритма O (N ^ 2), так как l[1:] создает новый список со ссылками на остальные элементы в списке.
Если вам нужна эффективность, я бы рекомендовал вам использовать списки (Haidro answer), но я полагаю, что это не приоритет, если вы хотите его только для обучения целей.
Вероятно, меньше pythonic, но там:
def recurseDecrMap(l):
return [l[0]-1] + recurseDecrMap(l[1:]) if l else []
Для чего это стоит, это ужасный способ узнать о рекурсии, потому что вы используете его для выполнения чего-то, что по своей сути не является рекурсивным. Если ваш учитель действительно просит вас написать программу, которая рекурсивно редуцирует элементы списка, такие как [1, 2, 3, 4], а затем позорить его/ее.
Как отметил Хайдро, наиболее путинский способ решить эту проблему состоит в том, чтобы просто перебирать список, используя понимание списка
[i - 1 for i in l]
Как цикл, это
def decr(l):
a = []
for i in l:
a.append(i - 1)
return a
Рекурсия полезна, если вы хотите решить ту же проблему на произвольных уровнях глубины. Например, скажем, что у вас есть что-то вроде [1, [2, 3], [[4], 5]], и вы хотели уменьшить число на 1, сохраняя структуру списка. В этом случае рекурсивное решение будет использовать итерационное решение для базового случая и вызовет себя для рекурсивного случая.
def decr_recursive(l):
a = []
for i in l:
if isinstance(i, list):
a.append(decr_recursive(i))
else:
a.append(i - 1)
return a
Это может быть легко изменено, если вы хотите поддерживать больше, чем просто списки или целые числа.
>>> decr([1, [2, 3], [[4], 5]])
[0, [1, 2], [[3], 4]]
Это проблема, которую очень сложно решить без использования рекурсии, но с ней легко решить. То, что вы задаете, - это проблема, которую легко решить без рекурсии (это просто простая итерация по списку ради Бога), но с ней трудно решить.
Некоторые причины, по которым вам следует избегать рекурсии в Python
Сложнее читать. Сравните [i - 1 for i in l] или даже явный цикл с чем-то вроде
def decr(l):
if not l:
return []
return [l[0] - 1] + decr(l[:1])
Вызов функции в Python может быть дорогостоящим. Я получаю примерно то же время, что и Ashwini Chaudhary на моем компьютере. Но [i - 1 for i in range(10**4)] занимает 559 мкс на моем компьютере. Это на три порядка быстрее, чем самый быстрый рекурсивный метод.
Рекурсивные функции не работают за 1000 вызовов, если вы не установили лимит рекурсии выше. Возможно, вы заметили ответ sys.setrecursionlimit(10**5) в ответе Ашвини Чаудхари. Это необходимо, потому что без него каждый вызов приведет к RuntimeError: maximum recursion depth exceeded после огромной трассировки. Но даже при этом немного больший список все равно приведет к ограничению рекурсии. И согласно документации, для каждой ОС существует верхний предел, и установка слишком высокой может привести к сбою.
Рекурсивные функции сложнее отлаживать. Они не только загрязняют трассировки стека сотнями вызовов от одной и той же функции, но их концептуально сложнее, потому что одна и та же часть используется по-разному, в зависимости от того, на каком уровне в стеке вы находитесь Естественный человеческий образ мышления является итеративным. Мы делаем все по одному. Наши "мозги" "стеки" всего лишь на несколько уровней, поэтому нам очень сложно решать проблемы рекурсивным способом, например "позвольте мне начать решение проблемы, но прежде чем закончить, позвольте мне решить еще одну проблему, а затем когда я закончу, я закончу оригинальную проблему. И в меньшей задаче я могу сделать то же самое, так что я получу несколько уровней до того, как закончу". Вот почему вы идете на кухню, чтобы получить ручку, затем вы видите конфету и начинаете есть, а когда вы закончите, вы забыли про перо. Вы "рекурсировали" уровень, от проблемы с пером до проблемы с конфетами, и ваш ментальный стек был слишком глубоким (всего два уровня, но этого достаточно). Если бы вы вместо этого схватили конфету, но прежде чем открыть ее и начать есть, также нашли ручку (лучший итеративный аналог, который я мог бы придумать), вы бы обошелись без забывания. То, как вы должны решать проблемы в программах, должно быть точно таким же, как вы их решаете в своей голове, потому что это единственный способ понять, что делает ваш код. Python - такой отличный язык, потому что его интерфейс высокого уровня позволяет вам делать именно это (по крайней мере, чаще, чем на языках более низкого уровня). Используйте этот факт!
Здесь худший способ - используя Компилятор с фиксированной точкой:
Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
recurseDecrMap = Y(lambda f: lambda l: [l[0]-1] + f(l[1:]) if l else [])
Вот простой питонический путь:
>>> mylist = range(30)
>>> def func(l):
... return [i-1 for i in l]
>>> func(mylist)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
Пояснение:
Я использовал список понятий, чтобы создать новый список каждого элемента в mylist, значение которого меньше, чем оно было.
Нет ничего плохого в вашей части кода, за исключением случаев, когда вы собираетесь использовать ее более одного раза:
>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
>>> recurseDecrMap(l)
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28]
Чтобы этого избежать, откройте этот ответ.
Сроки сравнения различных способов сделать это:
In [1]: import sys
In [2]: sys.setrecursionlimit(10**5)
In [3]: from so import *
In [4]: %timeit recur(range(10**4)).show()
10 loops, best of 3: 18.2 ms per loop
In [5]: %timeit recurse1(range(10**4))
1 loops, best of 3: 559 ms per loop
In [6]: %timeit recurse2(range(10**4))
1 loops, best of 3: 1e+03 ms per loop
In [7]: %timeit recurse3(range(10**4))
1 loops, best of 3: 1.02 s per loop
In [8]: %timeit recurse4(range(10**4))
1 loops, best of 3: 596 ms per loop
Код:
class recur:
# No extra memory is required in this method
def __init__(self,lis):
self.lis=lis
self.len=len(self.lis)
self.rec(0)
def show(self):
return self.lis
def rec(self,n):
if n!=self.len:
self.lis[n]-=1
self.rec(n+1)
def recurse1(l,lis=None):
lis=lis if lis is not None else []
if l:
lis.append(l[0]-1)
return recurse1(l[1:],lis)
else:
return lis
def recurse2(l):
return [l[0]-1] + recurse2(l[1:]) if l else []
def recurse3(l):
if len(l) == 0:
return []
else:
return [l[0] -1] + recurse3(l[1:])
def recurse4(l, x = []):
if len(l) == 0:
return []
else:
x.append(l[0] -1)
recurse4(l[1:], x)
return x
Здесь рекурсивное решение, которое может справиться с большими списками, не попадая в пределы глубины рекурсии. Используя деление и покоя, глубина рекурсии равна O (log (N)) в худшем случае по сравнению с O (N) с наивной рекурсией. Любая рекурсия - это плохой выбор техники для этой проблемы, хотя она тривиально решается с помощью простого цикла for.
def dec_list(xs, a, b):
if b == a + 1:
xs[a] -= 1
if a + 1 >= b: return
mid = (a + b) // 2
dec_list(xs, a, mid)
dec_list(xs, mid, b)
def dec(xs):
dec_list(xs, 0, len(xs))
xs = range(1001)
dec(xs)
print xs