< Back

Lecture 11 - Recursion

As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab11 
$ cd ~/cs170/labs/lab11 

Emacs Commands

It's Friday, so it's new Emacs commands!

Begin highlighting a region
Cut the line from the cursor to the end of the line


A recursive function is simply a function that contains a function call to itself. People tend to struggle with understanding recursion, with good reason most of the time. As a matter of fact, some of you may have inadvertently (or purposefully on occasion) written recursive functions, it is likey the case that you haven't seen the true power of recursion. Recursive functions allow us to break a problem into more managable pieces. While it might not always be the most efficient mechanism, it usually results in incredibly pretty code.

Lab Activity 1
Finding Min

The most important thing to realize about recursion is that ANY loop can be rewritten to use recursion. Sometimes, this process is easier than others. But understanding how you can convert a loop into a recursive statement can make writing future recursive expressions a lot easier.


Create a file find_min.py, and write a function find_min(a_list) in this file. This function should recursively compute the minimum value from a_list. For simplicity sakes, consult the loop version of find_min below.

  def find_min(a_list):
      curr_min = a_list[0]
      for index in range(1, len(a_list)):
          curr_value = a_list[index]
          if curr_value < curr_min:
	      curr_min = curr_value
      return curr_min


> find_min([1, 2, 0, 3, 4])
> find_min([1, 2, 3, 4, 5])
> find_min([2, 3, 1, 4, 5])

Lab Activity 2
Greatest Common Divisor

One of the oldest algorithms known is the Euclidean algorithm for computing the greatest common divisor of two numbers. GCD is used when simplifying fractions, and sounds like it should be pretty complicated. However, it is one of the most beautiful algorithms in existence.

Luckily, I showed you the loop version of this function last class, during the hand tracing exercises. If you need a jump start on how to get started, consult the function in Lecture 10.


Create a file called euclidean.py, and create a function gcd(a, b) which computes the greatest common common divisor of the integers a and b. The logical mechanism for this function would be to check every integer in the range [1, min(a, b)]. However, there is an elegant recursive definition that can compute the gcd:

\[ \begin{eqnarray} gcd(a, 0) &=& a \\ gcd(a, b) &=& gcd(b, a \% b) \end{eqnarray} \]

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)


>>> gcd(3, 6)
>>> gcd(6, 3)
>>> gcd(1, 9001)
>>> gcd(36, 84)


  • Your base case is that the integer b is 0. In this case, you want to return the value a.

  • Your recursive case is simply the recursive call with the value of b for parameter a, and the value a % b for the parameter b. Don't forget to return this value!



    Remember the Fraction class you wrote about three weeks ago? Well, there are some operations that might produce a non-simplified fraction. If you were to show this to a mathematician, you would likely give them an aneurism. Add the Euclidean GCD function to your fraction.py file, and use the computed GCD to simplify your fractions.

    Lab Activity 3

    One nice thing about recursive functions is that they can sometimes be more efficient. Last semester, we made you write the power function using a loop. However, this function uses on the order of n multiplications. Using recursion, we can improve things pretty well.


    In a file called power.py, create a function called power(x, y). This function should follow the following recursive definition for power, which should perform fewer multiplications:

    \[ \begin{eqnarray} x^1 &=& x\\ x^y &=& x ^ {\frac{y}{2}} \times x ^ {\frac{y}{2}} \mbox{ if y is even and greater than 1}\\ x^y &=& x \times x ^ {\frac{y-1}{2}} \times x ^ {\frac{y - 1}{2}} \mbox{ if y is odd and greater than 1} \end{eqnarray}\]

    You should also write a function called loop_pow(x, y), which computes the power using the traditional loop methodology. For both of these functions, you should return both the value of the power, and the number of multiplications required to compute the value. Test both functions, and make sure the recursive definition performs fewer multiplications.


    >>> power(2, 3)
    (8, ###)
    >>> loop_power(2, 3)
    (8, 2)
    >>> loop_power(2, 10)
    (1024, 9)
    >>> power(2, 10)
    (1024, ###)
    >>> power(9, 15)
    (205891132094649, ###)
    >>> loop_power(9, 15)
    (205891132094649, 14)

    Example censored to not spoil the surprise!


    Notice in the above recursive definition that while there are really two recursive calls to power, you only really need to perform one in each recursive case. You can store that value in a variable, and use that variable in your multiplications.



    How does this recursive definition compare in run times? Let's use a timer and plot the results! Try computing the powers of 2 from 1 to 500, and plot the results as you did in the last lab. If you are mind is not too melted after todays recursion lab, you can compare the performance of the ** operator to the above functions.


    When you have finished, create a tar file of your lab16 directory. To create a tar file, execute the following commands:

    cd ~/cs170/labs
    tar czvf lab11.tgz lab11/

    To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Lab Assignment 15. Make sure you include a header listing the authors of the file.

    In-Class Notes