Week of
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!)
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.
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) ------------------------------------------------------- """
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) ------------------------------------------------------- """
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) ------------------------------------------------------- """
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) ------------------------------------------------------- """
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) ------------------------------------------------------- """
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) ------------------------------------------------------- """