Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
Recursion is a very useful technique in many applications and forms the basis of efficient solutions using techniques such as memoization and dynamic programming.
It's also elegant and beautiful.
These notes are a sequence of exercises to help you to get used to thinking up recursive solutions to algorithmic probblems.
The thing about exercises is that watching someone else do them doesn't help you much. So I encourage you to actually try to fill in all the missing parts before looking at my solutions.
Each page in these notes illustrates the same design process for arriving at a solution. Most of the steps of this process aren't just good for applying recursion, but really for any programming problem that you come across. In day to day practice you may, do some of the steps in your head without writing anything down, however it's a good idea not to skip any steps, even if you just do them in your head. The process is this
In most of these excersises I've done some of the steps. As the exercises go on, I'll leave more and more steps out. You should fill in the missing steps.
I did all my coding in Python 3.5. You are welcome to use any language you want. It may be easiest to use Python, since my examples are in Python and my contracts are written in terms of Python's data types, but you can adapt the examples to any high-level language that you want.
The reasons I choose to use Python are several:
A nice surprise about Python was that it supports large integers natively. A less pleasant surprise was that, by default, Python limits recursion depth to a low number (1000 in my implementation); there are ways to increase this limit, but you risk crashing the interpreter if you increase it too much.
If you don't know Python, but want to use it anyway, it's really important to explicitly write out your pseudocode. That way you can think about the algoirthm without having to worry about the language, and then, later, figure our how to translate your algorithm into Python without having to worry about the design.
Jupyter notebook is a web application that lets you easily write web pages that contain code and also to execute that code and put the results into the web page. I'll say more about Jupyter Notebook on the next page.
What notation you use for peudocode isn't that important. I have my own notation which is explained in two documents:
I mention these documents mostly to help you understand my solutions, but you are free to adopt any aspects of my notation that you want.
I would encourage you to use immutable data types (sets and sequences) as much as possible. This keeps things simple. We can optimize later by using mutable data types if needed.
What do I mean by immutable and mutable. Here is an illustration in Python. Python has two native types for representing sequences: lists which are mutable and tuples which are immutable. Here we'll add an item to the right end of a sequence in two ways.
First using lists.
seq = [1,2,3]
seq.append(4)
seq
Now using tuples. (By the way, the funny looking (4,) is a tuple of length one.
seq = (1,2,3)
seq = seq + (4,)
seq
These look quite similar. But there is a significant difference. The append method changes (mutates) the list. Whereas the + (concatenate) operator creates a new tuple. This difference becomes important when there is more than one reference to the sequence, as illustrated below.
First using mutable lists.
anotherSeq = [1,2,3]
seq = anotherSeq
seq.append(4)
seq
anotherSeq
Now using immutable tuples.
anotherSeq = (1,2,3)
seq = anotherSeq
seq = seq + (4,)
seq
anotherSeq
The way we get multiple references is usually by passing arguments to parameters like this.
def append4( seq ) :
seq.append(4)
return seq
a = [1,2,3]
append4(a)
But now we have the (possibly unintended) side effect of changing the value of a.
a
Using immutable sequences prevents side effects like this. If I write.
a = (1,2,3)
the only way that a's value can change is if I assign to a. For example, I can't change it by calling append4 because that will lead to an error.
append4(a)
a
Let's try
def concatenate4( seq ) :
seq = seq + (4,)
return seq
concatenate4( a )
This function has no side effects. In particular we find that a has not been changed.
a
Functions with no side effects are called pure functions and are generally easier to reason about.
I could also make the function that expects a mutable list into a pure function by changing seq.append(4) to seq = seq + [4]. If I did that, I should document that the function does not alter the list parameter. For tuple parameters, it goes without saying that the tuple isn't changed, because you can not change tuples in Python.
For sets, Python also has mutable and immutable versions. Mutable sets in Python are of type set and immutable sets are of type frozen set.