Section 2: Natural Recursion
Table of Contents >
Chapter 2 > Section 2
We are now in a position to introduce the following data definition for a
list:
# ListOfX is one of:
# - []
# - [X] + ListOfX
# interp. a list of values of type X
L1 = []
L2 = [4, 3, 6]
# def fn_for_lox(lox):
# if lox == []:
# return ...
# else:
# return
...lox[0]...fn_for_lox(lox[1:])
Note that this is a parameterized data type. X
is a type
parameter that represents the type of data that will be stored in the
list. The above data definition is so commonly used that we assign
it the special notation (listof X)
. So, for example,
we could have a (listof str)
or (listof int)
or even (listof Account)
.
Let's examine this data definition a little more closely...
Notice that the types comment is
self-referential. We define
ListOfX
in terms of itself, as indicated by the arrow
above. Now notice that we have a corresponding
natural
recursion in the function template...
This is an example of how the shape of the data governs the shape of the
corresponding program. There is another sense in which this is true
for this data definition. Notice that the data definition has two
clauses and that the corresponding function template has two corresponding
clauses that are expressed with an
if-else
statement.
Now let's suppose that we wish to design a function that computes the sum
of a list of integers. By applying the HtDF design recipe, we arrive
at the code found in
Code
Explorer 2.1.
Now let's use our function to compute the sum of some lists of
integers. Note that we use the built-in Python functions
list
and
range
to quickly generate some sample lists. In
general,
list(range(n))
produces the list
[0, 1, 2,
..., n - 1]
.
>>> sum_loi((list(range(10)))
45
>>> sum_loi(list(range(100)))
4950
>>> sum_loi(list(range(1000)))
...
RuntimeError: maximum recursion depth exceeded
The final call results in a runtime error due to the fact that the
computation exceeds the maximum recursion depth allowed by the Python
interpreter. Note that each time we make a recursive call to the
sum_loi
function, the interpreter has to accumulate another piece of the
sum. So, if we pass the list
[4, 2, 6, 5, 1]
as an
argument to the
sum_loi
function, the following computation
is ultimately accumulated in memory:
(4 + (2 + (6 + (5 + 1))))
The brackets are included to illustrate the order in which the computation
is performed. This accumulation consumes memory and memory is a
finite resource. Python therefore imposes a limit on the depth of
the recursive calls that can be made. This does not mean that
recursion is not useful. Recursion represents a natural design for
functions that consume data that is self-referential. However,
if the size of that data is large, we may find that we exceed the depth of
recursive calls that is allowed in Python. In the next section, we
consider the use of tail-recursion to determine if it can be used as a
work-around for the limited depth of recursive calls. (It won't, but it
will get us one step closer to a solution to the problem!)