CSE1729 – Introduction to Programming
Spring 2019
Laboratory Assignment 2
Objectives
• Workwithrecursivefunctions
• Workwiththeconditionalifspecialform
Activities
1. Combinations: Often, we are interested in the number of ways a group of k objects can be formed from a total of n objects. For instance, if I needed to select three students from a lab section containing twenty students. How many ways are there to make this selection? First, notice that for the first student selected, I can choose any one out of the twenty in the section. Therefore, there are twenty ways to make this selection. For the second student, I am selecting from the nineteen remaining students. Therefore, there are nineteen ways to make this selection. Finally, I am making the selection of the last student from the remaining eigh- teen. So, there are eighteen ways to make the final selection. But, the ordering of our selections don’t make any difference. Consider the number of ways we can select a group of three students A, B and C. ABC, ACB, BAC, BCA, CBA and CAB give us six ways the same group of three have been counted. So, the total number of groups that can be counted is:
20·19·18
3·2·1
In general, we use the following equation to compute the number of groups of size k that can be formed
from n objects:
n!
(n −k)!k!
Youwillnoticethatthe(n−k)!terminthedenominatorcancelsthelast(n−k)termsintheproductofn!in
the numerator, leaving just the product of the top k terms from n !. Also notice, the k ! term prevents us from
counting the duplicate ways of selecting the same k objects. This computation has it’s own terminology and
notation. The notation is n and is read “n choose k ” indicating this quantity represents the number of ways k
of choosing k objects from a group of n objects. So,
n n!
k =(n−k)!k!
Use the factorial function discussed in lecture to write an (n-choose-k n k) function that takes two
parameters, n and k and computes the value of n shown above. k
Remark 1. Note that (n-choose-k n k) should evaluate to zero when n < k or k < 0.
2. Exponentiation Write a SCHEME procedure to compute b e by multiplying b a total of e times. Name your
function(pow b e).
3. Write a recursive function, named (zeno n), that computes the sum of the first n terms of the following
seriesfromZeno’sDichotomyParadox,Z =1+1+1+···+1.Useyour(powbe)functiontocompute n248 2n
the denominator of each term.
4. Number of Digits Write a SCHEME procedure, named (num-digits n), which accepts an integer n and returns the number of digits in n. For example, both (num-digits 10000) and (num-digits 12345) evaluate to 5.
1
5. YoungJeanieknowsshehastwoparents,fourgrandparents,eightgreatgrandparents,andsoon.
(a) Writearecursivefunction,named(a n)tocomputethenumberofJeanie’sancestorsinthenth previ- ous generation. The number of ancestors in each generation back produces a sequence that may look familiar:
2,4,8,16,...
For each generation back, there are twice the number of ancestors than in the previous generation back.
That is, an = 2an−1. Of course, Jeanie knows she has two ancestors, her parents, one generation back.
(b) Write a recursive function to compute Jeanie’s total number of ancestors if we go back n generations.
Specifically,(num-ancestors n)shouldreturn: 2+4+8+···+an
Useyourfunctioninpart(a)asa“helper”functioninthedefinitionof(num-ancestors n)1.
1 Of course, we can use the closed-form solution for the geometric progression to compute num-ancestors (a n c e s t o r s (n ) = 2n +1 − 2) but that doesn’t give us any experience with recursive functions. However, this is a useful fact we can use when testing our functions to ensure they are correct.
2