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
12345
then the output should be
54321
Fibonacci Write a program that computes the Fibonacci numbers Fni for a
sequence n0, . . . nk given in the standard input. See org/wiki/Fibonacci_number
For example if the input is
05
then the output should be
18
sinceF0 is1andF5 is8.
http://en.wikipedia.
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
yes
but 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 defined by:
|v| |u|
if |u| = 0, if |v| = 0,
otherwise.
d(u, v) = 1
d(u1, v) + 1 min d(u, v ) + 1
d(u1, v1) + f(u1, v1)
where |w| denotes the length of a sequence w; w1 denotes the suffix w2, w3, . . . of a sequence w = w1,w2,w3,…; w1 denotes the first element of a sequence w = w1,w2,w3,…; and f(e,e′) is 0 when e = e′ 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
