The goal of the following exercises is for you to familiarize with recursion.
All the exercises can be solved without recursion, but we suggest that you try
to use recursion. In all cases input is to be read from cin and the result is to
be provided to cout.
Reverse
Write a program that reverses a sequence of integers, as provided in
the standard input.
For example, if the input is
1 2 3 4 5
then the output should be
5 4 3 2 1
Fibonacci
Write a program that computes the Fibonacci numbers Fni for a
sequence n0, . . . nk given in the standard input. See http://en.wikipedia.
org/wiki/Fibonacci_number
For example if the input is
0 5
then the output should be
1 8
since F0 is 1 and F5 is 8.
Palindrome
Write a program that decides whether a sequence of integers is
a palindrome, i.e. if reading the sequence from right to left results in the very
same sequence.
For example, if the input is
13 22 33 22 13
then the output should be
yesbut if the input is
13 22 31
then the output should be
no
since the right-to-left reading is
31 22 13
Note that the right-to-left reading does not refer to individual digits, but to
entire numbers.
The Levenshtein distance
The Levenshtein distance between two sequences
of characters u = u1, u2, . . . , uk and v = v1, v2, . . . , vl is defifined by:
d(u, v) =
|v|
if |u| = 0,
|u|
if |v| = 0,
min
d(
u
1 , v
) + 1
d(
u, v
1
) + 1
d(u1 , v1 ) + f(u1, v1)
otherwise.
where |w| denotes the length of a sequence w; w1 denotes the suffiffiffix w2, w3, . . .
of a sequence w = w1, w2, w3, . . . ; w1 denotes the fifirst element of a sequence
w = w1, w2, w3, . . . ; and f(e, e0 ) is 0 when e = e0 and 1 otherwise.
As an example you can easily check that the distance d(“AB”, “B”) between
“AB” and “B” is 1 since:
d(“AB”, “B”) = min(d(“B”, “B”) + 1, d(“AB”, “”) + 1, d(“B”, “”) + 1) = min(1, 3, 2) = 1
d(“B”, “B”) = min(d(“”, “B”) + 1, d(“B”, “”) + 1, d(“”, “”) + 0) = min(2, 2, 0) = 0
d(“AB”, “”) = 2
d(“B”, “”) = 1
d(“”, “B”) = 1
Write a program that reads two words and returns their distance.
Challenges. Try to write a function that, given a set of elements, computes
all the possible permutations of the elements. Try to write a function that,
given a set, computes its powerset.
2
