recursion

[James Stroud]

Ian Clark wrote:
> Neil Cerutti wrote:
>> On 2007-09-13, Gigs_ <gigs at hi.t-com.hr> wrote:
>>> Can someone explain me this
>>>
>>>>>> def f(l):
>>>     if l == []:
>>>         return []
>>>     else:
>>>         return f(l[1:]) + l[:1]  # <= cant figure this, how is all 
>>> sum at the end?
>>
>> In plain English, the above program says:
>>
>> The sum of the items in list l is zero if the list is empty.
>> Otherwise, the sum is the value of the first item plus the sum of
>> the rest of the items in the list.
> 
> Am I missing something? What does this have to do with summing?
> 
>     >>> def f(l):
>     ...     if l == []:
>     ...         return []
>     ...     else:
>     ...         return f(l[1:]) + l[:1]
>     ...
>     >>> f([1, 2, 3, 4])
>     [4, 3, 2, 1]
> 
> Ian

Add it up!

Round   Sum

   0     f([1, 2, 3, 4])
   1     f([2, 3, 4]) + [1]
   2     f([3, 4]) + [2] + [1]
   3     f([4]) + [3] + [2] + [1]
   4     f([]) + [4] + [3] + [2] + [1]

Total   [] + [4] + [3] + [2] + [1] = [4, 3, 2, 1]

James