recursion

James Stroud jstroud at mbi.ucla.edu
Thu Sep 13 19:20:45 CEST 2007

```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

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

```