CP164 Lab 5 : Recursion

Week of

The Five Rules of Recursion

Even if you don't have an in-depth understanding of recursion, if you follow these five rules when creating a recursive function, you should still be successful in using recursion. (These rules are no substitute for understanding recursion!)

  1. Initialize everything. All parameters, variables, etc., should have values.
  2. Define at least one base case. The function must have at least one condition in which recursion stops.
  3. Define at least one general case. The function must have at least one condition where recursion - a recursive call - occurs.
  4. The recursive calls must move towards the base case. The function must have the possibility of reaching the base case, or it ends up with infinite recursion.
  5. NO LOOPS!!

Recursion With Single Values, Lists, and Strings

The basic structure of a simple recursive function looks something like this:

def recurse(value):

    if {base case condition is true}:
        # Base case - recursion stops.
        ans = {base case value}
    else:
        # General case - make recursive call.
        ans = {general value} + recurse({changed value})

    return ans

There are countless variations on this, but the basic approach is the same. The following example shows a function that calculates the sum of positive whole numbers from 1 to n :

def find_sum(n):

    if n == 1:
        # Base case.
        ans = 1
    else:
        # General case.
        ans = n + find_sum(n - 1)

    return ans

This fits the five rules: all variables and parameters are given values; there is one base case (when n is 1); there is one general case (when n >= 1); the recursive call moves towards the base case (1 is subtracted from n every call); and there are no loops. One variation of this code is:

def find_sum(n):
    ans = 1

    if n > 1:
        # General case (base case implied).
        ans = n + find_sum(n - 1)

    return ans

This version produces the same answer, but relies on a default value for ans as an implied base case rather than explicitly looking for it.

Strings can be used in recursive functions. The following function finds the length of a string recursively:

def str_len(s):

    if s == "":
        count = 0
    else:
        count = 1 + str_len(s[1:])

    return count

The key to understanding this function is in the recursive call. Every time the function calls itself it passes a smaller and smaller part of the string as an argument to the recursive call. Luckily in Python, s[1:] does not cause an error when only one character is left in the string - it simply returns an empty string ( "" ).

Lists and tuples can also be used with recursion. Interestingly, the previous function could be changed to return the length of a tuple or list by changing the line:

    if s == "":

to:

    if s == ():

and:

    if s == []:

respectively.

Put all functions into a library module named functions.py and test them from separate files.

  1. Write and test a function recurse that follows these rules:

    • if x < 0 or y < 0: f(x,y) = x - y

    • otherwise: f(x,y) = f(x-1,y) + f(x,y-1)

    The function signature is:

    def recurse(x, y):
        """
        -------------------------------------------------------
        Recursive function - example of tree recursion.
        Use: ans = recurse(x, y)
        -------------------------------------------------------
        Parameters:
            x - an integer (int)
            y - an integer (int)
        Returns:
            ans - the function result (int)
        -------------------------------------------------------
        """
    

    Test functions.py:


  2. The greatest common divisor (gcd) of two positive integers m and n can be defined recursively as follows:

    • if m % n == 0 , gcd(m, n) = n

    • otherwise: gcd(m, n) = gcd(n, m % n)

    The function signature is:

    def gcd(m, n):
        """
        -------------------------------------------------------
        Recursively find the Greatest Common Denominator of two numbers.
        Use: ans = gcd(m, n)
        -------------------------------------------------------
        Parameters:
            n - an integer (int)
            m - an integer (int)
        Returns:
            ans - the function result (int)
        -------------------------------------------------------
        """
    

    Test functions.py:


  3. Rewrite the following function as a recursive function, keeping the same name and number of parameters:

    def vowel_count(s):
        vowels = "aeiou"
        count = 0
    
        for c in s:
            if c.lower() in vowels:
                count = count + 1
    
        return count
    

    The function signature is:

    def vowel_count(s):
        """
        -------------------------------------------------------
        Recursively counts number of vowels in a string.
        Use: count = vowel_count(s)
        -------------------------------------------------------
        Parameters:
            s - string to examine (str)
        Returns:
            count - number of vowels in s (int)
        -------------------------------------------------------
        """
    

    Test functions.py:


  4. Write and test a recursive function that calculates a base value to a power. Example: 2^3 is 8. (2 is the base, 3 is the power). It should work with negative and positive bases and powers.

    The function signature is:

    def to_power(base, power):
        """
        -------------------------------------------------------
        Calculates base^power.
        Use: ans = to_power(base, power)
        -------------------------------------------------------
        Parameters:
            base - base to apply power to (float)
            power - power to apply (int)
        Returns:
            ans - base ^ power (float)
        -------------------------------------------------------
        """
    

    Test functions.py:


  5. Write a recursive version of the palindrome function. It should ignore non-letters and case. (Hint: use isalpha() .)

    The function signature is:

    def is_palindrome(s):
        """
        -------------------------------------------------------
        Recursively determines if s is a palindrome. Ignores non-letters and case.
        Use: palindrome = is_palindrome(s)
        -------------------------------------------------------
        Parameters:
            s - a string (str)
        Returns:
            palindrome - True if s is a palindrome, False otherwise (boolean)
        -------------------------------------------------------
        """
    

    Test functions.py:


  6. Write a recursive function bag_to_set that takes a list as a parameter and returns a new list in which the values that were in the old list appear only once in the new list (the order should be preserved). Sample data:

    Old list: [4, 5, 3, 4, 5, 2, 2, 4]
    New list: [4, 5, 3, 2]
    

    The function signature is:

    def bag_to_set(bag):
        """
        -------------------------------------------------------
        Copies elements of a bag to a set.
        Use: new_set = bag_to_set(bag)
        -------------------------------------------------------
        Parameters:
            bag - a list of values (list)
        Returns:
            new_set - containing one each of the elements in bag (list)
        -------------------------------------------------------
        """
    

    Test functions.py: