How expensive are list and tuple slicing?

[Alex]

Tim Peters wrote:

> [Alex]
>> Does slicing a list allocate memory at the point of the slice, or does
>> python implement some sort of copy on write scheme to save memory?  How
>> about tuples (which are immutable)?
> 
> Same answer for both:  x[i:j] takes time and space proportional to j-i; a
> new and independent object is created.
> 
>> Example: The following snippet of code counts the number of items in a
>> sequence.  It is obviously a very stupid way of doing this.  Neither the
>> sequence, nor any of its slices, are ever modified.
> 
> Doesn't matter.
> 
>> How much memory does it consume if the sequence is a list?
> 
> Proportional to len(sequence)**2.
> 
>> A tuple?
> 
> The same, but with a smaller proportionality constant because an N-element
> tuple requires a little less space than an N-element list in CPython.
> 
>> Is the behavior the same on Python and Jython?
> 
> Pretty much, yes.
> 
>> def count(sequence):
>>   if len(sequence)==1:
>>     return 1
>>   return count(sequence[:1])+ count(sequence[1:])
> 
> The "count(sequence[:1])" part doesn't contribute to the quadratic growth.

Thanks.  I guess that means I had better take care when writing recursive
functions that operate on large lists.