Tag Archives: Week 5

Week 5 – Think recursion

This post describes my difficulties in learning recursion and the resulting mental model I developed to deal with recursion in programming.

How I was introduced to recursion

As normal, I entered Danny’s lecture last Monday and was courteously told to grab and read a handout from the front desk – Danny told us we would be tracing code today -“nothing out of the commonplace” I thought to myself. I read the handout:

Recursion Exercises

I was curious, I was uneasy with that term, I was familiar with the term enough to use it but its meaning escaped my mind. I read on to find a function that called itself.

def sum_list(L):
    if isinstance(L, list):
        return sum([sum_list(x) for x in L])
    else:
        return L

I felt confused at first. Is this even legal syntax? I was quick to open my python console

user147-185:~ soohamrafiz$ python3

Python 3.4.2 (v3.4.2:ab2c023a9432, Oct  5 2014, 20:42:22)

[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin

Type "help", "copyright", "credits" or "license" for more information.

>>> def a():

...     return a()

...

>>> a()
...
...
Traceback (most recent call last):

File "", line 1, in 

File "", line 2, in a

RuntimeError: maximum recursion depth exceeded

Even though Danny told me this code was perfectly legal, I believed my compiler more. I would say I learnt nothing from my lecture.

But as scientists we should be open to change. A bad scientist is the one unable to believe he is wrong.

I laid the ground work on tackling my problem dealing with recursion.

  1. Understand what is recursion
  2. Learn how this property is used in real life
  3. Gain enough knowledge to build my own use of recursion

Achieving these 3 steps would teach me enough to use recursion in real life.

What is recursion and recursiveness?

I understood recursion from the example above to be the following:

A recursive program is a program that references (places a function call to) itself.

A recursive program is said to use recursion

The definition, while concrete still had a magical sense to? why would this (if ever) be useful?

How is recursive code used in real life?

I found answering this question to be initially tricky. The program I wrote above was also recursive yet failed to work.

It gave me the error.

RuntimeError: maximum recursion depth exceeded

What does one mean to exceed “maximum recursion depth” and how can we prevent this error from arising? I referred to a programming book called “Think Python” by Allen Downey. Using the example code from the book:

# Code by (Downey 2012)

# Shared under Creative Commons Attribution Non-Commercial 3.0 License
# which means I am free to use it as long as I reference the author below
# Reference MLA at bottom of post

 def countdown(n):
    if n <= 0:
        print "Blastoff"
    else:
        print n
        countdown(n-1)

if we call countdown as

countdown(2)

The function will print “2” and call itself with the original argument minus 1.

countdown(1)

and one more time till we reach 0.

countdown(0)

which prints “Blastoff!”.

I realised that all recursive functions have to have a terminating case – a Base case – which all arguments reach in order for the function to reliably work. In this case all positive inputs will eventually reach the base case of n=0.

Unless the input is a negative number.

countdown(-1)

this never reach 0 and the function will never terminate. The same case happened with my own program at the start.

The python compiler was taught to catch such errors and will automatically terminate after a certain number of recursive calls as defined by

sys.getrecursionlimit()

function in the sys module (Python Software Foundation).

By the end of this I thought of successful recursion as proof by induction in mathematics.

As long as:

(\exists a \in \mathbb{Z}, \text{input a terminates}) \wedge (\forall n \geq a, \text{input n terminates} \implies \text{input n+1 terminates})

Then the recursive code should terminate for all cases bigger than a.

Writing my own example of recursion

To find a good example to practice on I searched online for “recursion exercises”, I found that the dot product of two vectors could be implemented recursively.

Take the two vectors in \mathbb{R}^n,  V = \left[\begin{matrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{matrix}\right] and U = \left[\begin{matrix} u_1 \\ v_2 \\ \vdots \\ u_n \end{matrix}\right]

Then the dot product V \cdot U = \displaystyle\sum_{i=1}^{n} v_iu_i.

recursively, we can define the dot product as:

  1. The dot the product of two empty vectors is 0
  2. The dot the product of two non-empty vectors is the product of the first element from both vectors added to the dot product of the remaining vectors.

In python

def dot_product(v, u):
    """ (list of num, list of num) -> num
        Returns the dot product of the two vectors v and u.
        Precondition: len(v) == len(u)
    """
    try:
        if v == [] and u == []:
            return 0
        else:
            return v[0]*u[0] + dot_product(v[1:], u[1:])
    except IndexError:
         # the length of the vectors not the same
         print('The length of the vectors is not the same')
         return None
    except TypeError:
         # There is an incorrect type used
         print("Incorrect type!")
         return None

And now I got the hang of recursion! 😀

References

Downey, Allen. “5.8 Recursion.” Think Python. Sebastopol, CA: O’Reilly, 2012. 44-45. Print.

Python Software Foundation. “28.1. Sys — System-specific Parameters and Functions.” 28.1. Sys. Python Software Foundation, n.d. Web. 01 Feb. 2015. <https://docs.python.org/2/library/sys.html&gt;.

Standard