Description
This Lab exercise introduces you to a powerful problem solving method using functional recursion.
Recursion refers to an abstraction that is defined in terms of itself. Examples include mathematical
abstractions such as Fibonacci series, Factorials, and Exponentials, and other abstractions such as the Towers
of Hanoi puzzle, the Eight Queens problem and Fractal Geometry. Many interesting and challenging
computational problems that are difficult to solve in an iterative fashion are very simple and elegant to solve
using recursive function calls. Following the methods discussed in class, you should begin to get a feel for
“thinking recursively”.
Warm-up
1) Consider the following simple recursive function:
def foo(n):
if n<1:
print(”)
else:
print(‘*’,end=”)
foo( n-1 )
Discuss the following questions with your lab partner(s). Do not attempt the remainder of this lab exercise
until you are able to answer them and are comfortable with the concepts:
a. Describe what this function does, given an integer value for n.
b. Every recursive function must contain at least one base case. What is the base case for the function
foo()?
c. Why is this considered a “base case”?
d. Every recursive function includes a “reduction” step that always moves closer to one of the base cases.
Will the reduction step in the foo() function move closer to the base case under all circumstances? Explain
why or why not.
e. What distinguishes a “base case” from a “reduction step” in a recursive function definition?
2) Consider the following: “construct a recursive function to display the digits of an integer in reverse order
on the console display”. This is a non-pure function (procedure) that takes a single integer argument:
def reverseNum(n):
and, given an integer value such as:
reverseNum(5786);
will output the following to the console display:
6875
Construct the reverseNum function:
a. Start by identifying a base case that is trivial to solve. For this problem, perhaps the easiest integer to
“reverse” would be any value with a single digit. In this case, you would simply display the input value and
be done. Write the Python statement or statements to implement the base case and return.
b. Next, determine if there is some way the original problem can be represented as a simple sub-problem
combined with some simple operation. For this particular problem, note that if the argument contains more
than one digit, reversing it entails displaying the rightmost digit first, followed by the rest of the digits in
reverse order. The “rest of the digits in reverse order” is simply a sub-problem of the original problem!
First, write the Python statement or statements that will display the “rightmost” digit.
c. Now, write the recursive reduction step that calls the function for the “rest of the digits”.
d. Combining these two steps forms the complete reduction case. If this is the only reduction step, it is
simply performed for any but the base case(s). Complete the else clause from a) to form the entire reduction
step.
e. Before you complete and test the function, take a minute to ensure that a) the base case represents a correct
solution, and b) the reduction step is guaranteed to get you “closer” to the base case. Now combine the base
and reduction steps and write the complete function definition.
3) Write a recursive function to determine the maximum value in a list of integers (without using the built-in
function max. The function declaration is:
def maxValue( vals ):
where vals is a list of integers.
a. First, describe the base case: [hint: in what size list would it be easiest to find the maximum value? and
which value would it be?]
b. Next, describe the reduction step: [hint: describe the original problem using a simple case in combination
with some reduced form of the problem. Also consider how you would obtain a “smaller” list.
c. Describe why the reduction step will 1) solve the problem and 2) move closer to the base case:
d. Now, write and test the complete function definition for maxValue
Stretch
1) Fibonacci Numbers
Fibonacci numbers are integers derived from the Fibonacci Series:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, . . .
named for Leonardo Fibonacci who described it formally in the early 13th century. However, this series is
traced to the mathematics of ancient India where it was used to describe patterns of Sanskrit syllables. More
than a mathematical curiosity, Fibonacci numbers appear often in many biological patterns such as the spiral
of seeds in sunflowers, the arrangement of pinecone and pineapple florets, the branching of trees and the
number of petals on flowers to name just a few. Each of these biological patterns have their bases in the
Fibonacci Sequence.
Mathematically, the Fibonacci sequence is described recursively:
Fn = Fn-1 + Fn-2
F0 = 0
F1 = 1
Construct a recursive function named fibonacci that will take an integer value n as an argument and
return Fn , and then write a short program that will call your function to print out the first 20 Fibonacci
numbers.
2) Fractal Trees
Consider the following function that uses recursion to draw a “tree” using Turtle graphics:
def tree(t, trunkLength):
if trunkLength < 5:
return
else:
t.forward(trunkLength)
t.right(30)
tree(t, trunkLength-15)
t.left(60)
tree(t, trunkLength-15)
t.right(30)
t.backward(trunkLength)
Implement this function and try it out with a branch length of 100 (recall that you can speed up the drawing
by using the .speed turtle method). It generates a symmetric drawing resembling a “tree”. However no real
trees actually grow this way! When a tree creates a new branch, there is some bounded randomness to the
direction and length of each branch.
Modify the tree function so it will choose new branching angles between 15 and 45 degrees, and generate
branches that are between 12 and 18 units shorter than their “parent” branches. [you will need to use the
random module]
Now the output should look a bit more like a “real” tree. Go ahead and try different random ranges for the
branches and angles. See if you can create more “lifelike” trees. It’s fun!
Workout
1) Binomial Coefficient
In probability and statistics applications, you often need to know the total possible number of certain outcome
combinations. For example, you may want to know how many ways a 2-card BlackJack hand can be dealt
from a 52 card deck, or you may need to know the number of possible committees of 3 people that can be
formed from a 12-person department, etc. The binomial coefficient (often referred to as “n choose k”) will
provide the number of combinations of k things that can be formed from a set of n things. The binomial
coefficient is represented mathematically as:
which we refer to as “n choose k”. The naïve approach to computing the binomial coefficient is to use
factorials:
However, this approach is computationally infeasible for all but the simplest problems because factorials
quickly become too large to be represented by any numerical variables. For example if you wanted to know
the number of BlackJack hands that can be dealt from 3 decks of cards shuffled together, the factorial (52*3)!
is not computable using the naïve approach! Fortunately, the definition for the binomial coefficient can be
expressed as a recurrence:
Write a recursive function named choose(n,k) that will compute and return the value of the binomial
coefficient given the integer values n and k.
Write a short Python program that will input values for n and k, call your recursive function and then output
the results.
Use your program to determine the number of 5-card poker hands that can be dealt from a 52 card deck.
Use your program to determine the number of 2-card blackjack hands that can be dealt from three 52 card
decks all shuffled together.
Challenge
Here is an interesting challenge problem. Try it if you have extra time or would like additional practice
outside of lab.
1) Euclidean GCD
The Greatest Common Divisor of two integers a and b, GCD(a,b), not both of which are zero, is the largest
positive integer that divides both a and b. The Greek philosopher and mathematician Euclid devised an
incredibly clever and efficient algorithm to determine the GCD of two integers using a minimum number of
steps.
The Euclidean algorithm for finding the Greatest Common Divisor of a and b is as follows:
If b=0, then GCD(a,b) = a.
Otherwise, divide a by b to obtain an integer quotient q and remainder r. By definition, a = bq + r.
Since GCD(a,b) = GCD(b,r), simply replace a with b and b with r and repeat the procedure.
Note carefully that the remainders are decreasing at each iteration, therefore a remainder of 0 will eventually
result. The last nonzero remainder is GCD(a,b).
Example: GCD(1260,198): a=1260, b=198
GCD(1260,198) 1260 = 198 x 6 + 72 b=198, r=7 = GCD(198,72)
GCD(198,72) 198 = 72 x 2 + 54 b=72, r=54 = GCD(72,54)
GCD(72,54) 72 = 54 x 1 + 18 b=54, r=18 = GCD(54,18)
GCD(54,18) 54 = 18 x 3 + 0 b=18, r=0 = GCD(18,0)
GCD(18,0) = 18 (by rule 1)
Write a recursive implementation of the Euclidean GCD function: gcd(a, b)
Write a program that reads two integers and then calls a recursive implementation of the Euclidean GCD
function: gcd(a, b)that calculates and returns the greatest common divisor of a and b. Display the two
integers and the greatest common divisor on the terminal screen.
Note: a must be greater than or equal to b. If a < b, simply return GCD(b,a). If either a or b is negative,
replace it with its absolute value.
