Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
aList = ['r' 'e', 'c', 'u', 'r', 's', 'i', 'o', 'n']
len( aList )
aTuple = ('w' 'o', 'n', 'd', 'e', 'r', 'l', 'a', 'n', 'd') ;
len( aTuple )
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
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
Complete the following function
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.
length( () )
length( (42,) )
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
post result is the length of $s$.if $s = [\,]$ then 0
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
post result is the length of $s$.if $isEmpty(s)$ then 0
else $1 + length( rest(s) )$
end if
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
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 ) )
lengthMine( () )
lengthMine( (42,) )
lengthMine( (6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128,
2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216 ) )
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.