recursion

[Neil Cerutti]

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.

Well, it would say that if it weren't somewhat buggy. l[:1]
doesn't evaluate to a number, but to a list containing one
number, so the above program doesn't do what you say it does.

It should read something like:

 def my_sum(seq):
   if len(seq) == 0:
     return 0
   else:
     return seq[0] + my_sum(seq[1:])

The tough part of recursion is the leap of faith required to
believe that it works. However, you can often use an inductive
proof of correctness to help obviate the faith.

Proof that my_sum(seq) computes the sum of the items in seq (this
proof is modeled on proofs written by Max Hailperin, Barbara
Kaiser, and Karl Knight, in _Concrete Abstractions_):

  Base case: my_sum(seq) terminates with value 0 when len(seq) is
  zero, because of the evaluation rules for if, len and ==.

  Induction hypothesis: Assume that my_sum(subseq) evaluates to
  the sum of all the items in subsequence of seq, where 0 <=
  len(subseq) < len(seq).

  Inductive step: Consider evaluating my_sum(seq) where the
  length of seq is greater than 0. This will terminate if
  my_sum(seq[1:]) terminates, and will have the value of seq[0] +
  my_sum(seq[1:]). Because seq[1:] evaluates to the subsequence of
  the rest of the items in seq (all except the first), and 0 <=
  len(subseq) < len(seq), we can assume by our induction
  hypothesis that my_sum(seq[1:]) does terminate, with a value
  equal to the sum of the the rest of the items in seq.
  Therefore, seq[0] + my_sum(seq[1:]) evaluates to seq[0] + the
  sum of all the items in seq[1:]. Because seq[0] + the sum of
  the rest of the items in seq equals the sum of all the items in
  seq, we see that my_sum(seq) does terminate with the correct
  value for any arbitrary length of seq, under the inductive
  hypothesis of correct operation for subsequences of seq.

  Conclusion: Therefore, by mathematical induction on the length
  of seq, my_sum(seq) terminates with the value of the sum of all
  the items in seq for any length of seq.

But really I prefer the first first plain English version. ;)

-- 
Neil Cerutti
For those of you who have children and don't know it, we have a nursery
downstairs. --Church Bulletin Blooper