Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

In [14]:

```
aList = ['r' 'e', 'c', 'u', 'r', 's', 'i', 'o', 'n']
len( aList )
```

Out[14]:

In [15]:

```
aTuple = ('w' 'o', 'n', 'd', 'e', 'r', 'l', 'a', 'n', 'd') ;
len( aTuple )
```

Out[15]:

But let's suppose Python didn't have a length function. How can we write one using recursion.

This isn't something I'd normally do, at least not in Python, but the point of these exercises is to get comfortable with recursion, not to learn the best way to solve problems.

Python has several built-in types for representing sequences and more can be added by class defnitions. The built-in types include `tuple`

, `list`

, `string`

, `bytes`

, and `bytearray`

. I'm going to use tuples mostly. To make the code less dependent on the details of Python, we'll make and use the following definitions

In [38]:

```
def isEmpty( s ):
"""Pre: s is a sequence represented by a tuple
Post: result is true if s is empty and false otherwise
"""
assert isinstance(s, tuple)
return s == ()
def cons( x, s ) :
"""Pre: s is is a sequence represented by a tuple
Post: result is a sequence represented by a tuple with x as its first item and s as the rest.
"""
assert isinstance(s, tuple)
return (x,) + s
def first( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result the first item of the sequence
"""
assert isinstance(s, tuple) and s != ()
return s[0] ;
def rest( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result the first item of the sequence
"""
assert isinstance(s, tuple) and s != ()
fst, *rst = s
return tuple(rst);
def decons( s ) :
"""Pre: s is is a nonempty sequence represented by a tuple
Post: result is a pair consisting of the first items of s and a tuple of the rest of the items
"""
assert isinstance(s, tuple) and s != ()
fst, *rst = s
return fst, tuple(rst)
```

We write a contract for a `length`

function which will find the length of a sequence represented by a tuple.
The contract is

```
def length( s ):
"""
Pre: s is a sequence
Post: result == length of the sequence
"""
```

Alice notices (rather obviously) that if we split a sequence into its first item and a sequence of all the rest of the items then the length of the list is one more than the length of rest of the sequence. For example if we hae a sequence $[a,b,c,d]$ then and split it into the first item $a$ and the rest of the sequence $[b,c,d]$, the length of the original list will be one more than the length of $[b,c,d]$.

The empty sequence can't be split, so it must be a base case.

Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want or skip it if you don't.

*[Put your pseudocode here]*

Before coding, you should check that your design will work. Here is a checklist

- Is every case allowed by the precondition covered?
- Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
- Is there a variant function?

Complete the following function

In [26]:

```
def length( s ):
"""
Pre: s is a sequence
Post: result == length of the sequence
"""
```

If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

In [27]:

```
length( () )
```

In [28]:

```
length( (42,) )
```

In [29]:

```
length( (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128,
2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216 ) )
```

Here is my pseudocode, it's included here mostly as an illustration of the notation that I use for sequences when writing pseudocode

function$length( s : seq)$

pre$s$ is a sequence

postresult is the length of $s$.

if$s = [\,]$then0

else$1 + length( s[1,..] )$

end if

or using the functions defined above, we could write

function$length( s : seq)$

pre$s$ is a sequence

postresult is the length of $s$.

if$isEmpty(s)$then0

else$1 + length( rest(s) )$

end if

- A sequence is either empty or not, so all cases are covered
- The code looks right for both cases.
- The variant function is the length of the sequence $s$!

Remark. This is an unusual case where the function we are computing and the variant function itself are the same thing. Nevertheless it works.

And here is the Python 3 code

In [42]:

```
def lengthMine( s ):
"""
Pre: s is a sequence
Post: result == length of the sequence
"""
if isEmpty( s ) : return 0
else: return 1 + lengthMine( rest( s ) )
```

In [43]:

```
lengthMine( () )
```

Out[43]:

In [44]:

```
lengthMine( (42,) )
```

Out[44]:

In [45]:

```
lengthMine( (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128,
2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216 ) )
```

Out[45]:

As mentioned above, this is not a sensible way to find the length of a sequence in Python, given that there is a built in function to do the same thing.