On Fri, 17 Jun 2011 16:45:38 +0200, Franck Ditter wrote: > Hi, I'm just wondering about the complexity of some Python operations > to mimic Lisp car and cdr in Python... > > def length(L) : > if not L : return 0 > return 1 + length(L[1:])
Python's lists are arrays/vectors, not linked lists. > Should I think of the slice L[1:] as (cdr L) ? No. > I mean, is the slice a copy of a segment of L, Yes. > or do I actually get a pointer to something inside L ? No. > Is the above function length O(n) or probably O(n^2) ? O(n^2). And Python doesn't do tail-call optimisation, so you're likely to run out of stack for a large list. -- http://mail.python.org/mailman/listinfo/python-list
