You are here:   ArielOrtiz.com > Programming Languages > Recursive Functions, Part II

# Recursive Functions, Part II

## Objectives

During this activity, students should be able to:

• Write recursive functions of medium complexity using the Clojure programming language.

This activity helps students develop the following skills, values and attitudes: ability to analyze and synthesize, capacity for identifying and solving problems, and efficient use of computer systems.

## Activity Description

This activity can be developed individually or in pairs.

Solve the following set of programming exercises using Clojure. Place all your functions in a file called `recursion2.clj`. All problems should be solved using explicit recursion or the `recur` and `loop` special forms.

1. The function `my-repeat` takes a number `n` and any data `x` as its arguments. It returns a list that contains `n` copies of `x`. Do not use the predefined `repeat` function. Unit tests:
```(deftest test-my-repeat
(is (= () (my-repeat 0 'x)))
(is (= '(6 6 6) (my-repeat 3 6)))
(is (= '((ha ha) (ha ha) (ha ha)) (my-repeat 3 '(ha ha))))
(is (= '(true true true true true) (my-repeat 5 true))))
```
2. The function `invert-pairs` takes as an argument a list of vectors containing two elements each. It returns a new list with every vector pair inverted. Unit tests:
```(deftest test-invert-pairs
(is (= () (invert-pairs ())))
(is (= '([1 a][2 a][1 b][2 b]))(invert-pairs '([a 1][a 2][b 1][b 2])))
(is (= '([1 January][2 February][3 March])
(invert-pairs '([January 1][February 2][March 3])))))
```
3. The function `enlist` surrounds in a list every upper-level element of the list it takes as input. Unit tests:
```(deftest test-enlist
(is (= () (enlist ())))
(is (= '((a) (b) (c)) (enlist '(a b c))))
(is (= '(((1 2 3)) (4) ((5)) (7) (8)) (enlist '((1 2 3) 4 (5) 7 8)))))
```
4. The function `my-interleave` takes two arguments: the lists `a` and `b`. It returns a list containing the first element of `a`, followed by the first element of `b`, followed by the second element of `a`, followed by the second element of `b`, and so on. The lists `a` and `b` don't have to be of the same size. The interleaving of the elements stops when either `a` or `b` is exhausted. Do not use the predefined `interleave` function. Unit tests:
```(deftest test-my-interleave
(is (= () (my-interleave () ())))
(is (= () (my-interleave '(a) ())))
(is (= () (my-interleave () '(1))))
(is (= '(a 1 b 2 c 3 d 4 e 5) (my-interleave '(a b c d e) '(1 2 3 4 5))))
(is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d e) '(1 2 3 4))))
(is (= '(a 1 b 2 c 3 d 4) (my-interleave '(a b c d) '(1 2 3 4 5))))
(is (= '(a 1) (my-interleave '(a) '(1 2 3 4 5))))
(is (= '(a 1) (my-interleave '(a b c d e) '(1)))))
```
5. The function `my-flatten` removes all the interior parenthesis of the list it takes as input. Do not use the predefined `flatten` function. Unit tests:
```(deftest test-my-flatten
(is (= () (my-flatten ())))
(is (= '(a b c d e) (my-flatten '((a b) ((c) d (e))))))
(is (= '(one two three four)
(my-flatten '(((one) ((two))) () (three (())) four)))))
```
6. The function `exchange` takes three arguments: two non-list values `x1` and `x2`, and a list `lst`. It returns a list with the same elements as `lst`, except that all occurrences of `x1` are replaced by `x2` and vice versa, including any occurrences inside nested lists. Unit tests:
```(deftest test-exchange
(is (= () (exchange 'x 'y ())))
(is (= '(d b c a) (exchange 'a 'd '(a b c d))))
(is (= '((42) true ((cool (true)) (42))))
(exchange true 42 '((true) 42 ((cool (42)) (true))))))
```
7. The function `insert` takes two arguments: a number `n` and a list of numbers `lst` in ascending order. It returns a new list with the same elements as `lst` but inserting `n` in its corresponding place. Unit tests:
```(deftest test-insert
(is (= '(14) (insert 14 ())))
(is (= '(4 5 6 7 8) (insert 4 '(5 6 7 8))))
(is (= '(1 3 5 6 7 9 16) (insert 5 '(1 3 6 7 9 16))))
(is (= '(1 5 6 10) (insert 10 '(1 5 6)))))
```
8. The function `my-sort` takes an unordered list of numbers as an argument, and returns a new list with the same elements but in ascending order. You must use the `insert` function defined in the previous exercise to write the `my-sort`. Do not use the predefined `sort` function. Unit tests:
```(deftest test-my-sort
(is (= () (my-sort ())))
(is (= '(0 1 3 3 4 6 7 8 9) (my-sort '(4 3 6 8 3 0 9 1 7))))
(is (= '(1 2 3 4 5 6) (my-sort '(1 2 3 4 5 6))))
(is (= '(1 5 5 5 5 5 5) (my-sort '(5 5 5 1 5 5 5)))))
```
9. The function `binary` takes an integer `n` as input (assume that `n` ≥ 0). If `n` is equal to zero, it returns an empty list. If `n` is greater than zero, it returns a list with a sequence of ones and zeros equivalent to the binary representation of `n`. Unit tests:
```(deftest test-binary
(is (= () (binary 0)))
(is (= '(1 1 1 1 0) (binary 30)))
(is (= '(1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1) (binary 45123))))
```
10. The function `prime-factors` takes an integer `n` as input (assume that `n` > 0), and returns a list containing the prime factors of `n` in ascending order. The prime factors are the prime numbers that divide a number exactly. If you multiply all the prime factors you get the original number. Unit tests:
```(deftest test-prime-factors
(is (= () (prime-factors 1)))
(is (= '(2 3) (prime-factors 6)))
(is (= '(2 2 2 2 2 3) (prime-factors 96)))
(is (= '(97) (prime-factors 97)))
(is (= '(2 3 3 37) (prime-factors 666))))
```
11. The function `compress` takes a list `lst` as its argument. If `lst` contains consecutive repeated elements, they should be replaced with a single copy of the element. The order of the elements should not be changed. Unit tests:
```(deftest test-compress
(is (= () (compress ())))
(is (= '(a b c d) (compress '(a b c d))))
(is (= '(a b c a d e) (compress '(a a a a b c c a a d e e e e))))
(is (= '(a) (compress '(a a a a a a a a a a)))))
```
12. The function `pack` takes a list `lst` as its argument. If `lst` contains consecutive repeated elements they should be placed in separate sublists. Unit tests:
```(deftest test-pack
(is (= () (pack ())))
(is (= '((a a a a) (b) (c c) (a a) (d) (e e e e))
(pack '(a a a a b c c a a d e e e e))))
(is (= '((1) (2) (3) (4) (5)) (pack '(1 2 3 4 5))))
(is (= '((9 9 9 9 9 9 9 9 9)) (pack '(9 9 9 9 9 9 9 9 9)))))
```
13. The function `encode` takes a list `lst` as its argument. Consecutive duplicates of elements in `lst` are encoded as vectors [`n` `e`], where `n` is the number of duplicates of the element `e`. Unit tests:
```(deftest test-encode
(is (= () (encode ())))
(is (= '([4 a] [1 b] [2 c] [2 a] [1 d] [4 e])
(encode '(a a a a b c c a a d e e e e))))
(is (= '([1 1] [1 2] [1 3] [1 4] [1 5]) (encode '(1 2 3 4 5))))
(is (= '([9 9]) (encode '(9 9 9 9 9 9 9 9 9)))))
```
14. The function `encode-modified` takes a list `lst` as its argument. It works the same as the previous problem, but if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are converted to [`n` `e`] vectors. Unit tests:
```(deftest test-encode-modified
(is (= () (encode-modified ())))
(is (= '([4 a] b [2 c] [2 a] d [4 e])
(encode-modified '(a a a a b c c a a d e e e e))))
(is (= '(1 2 3 4 5) (encode-modified '(1 2 3 4 5))))
(is (= '([9 9]) (encode-modified '(9 9 9 9 9 9 9 9 9)))))
```
15. The function `decode` takes as its argument an encoded list `lst` that has the same structure as the resulting list from the previous problem. It returns the decoded version of `lst`. Unit tests:
```(deftest test-decode
(is (= () (decode ())))
(is (= '(a a a a b c c a a d e e e e)
(decode '([4 a] b [2 c] [2 a] d [4 e]))))
(is (= '(1 2 3 4 5) (decode '(1 2 3 4 5))))
(is (= '(9 9 9 9 9 9 9 9 9) (decode '([9 9])))))
```

Source of many of these problems: Ninety-Nine Lisp Problems

## Deliverables

Deliver a single file called `recursion2.clj` containing your solutions and the unit tests. Please provide the following information:

Only one team member needs to upload the file.

IMPORTANT: The program source file must include at the top the authors’ personal information (name and student id) within comments. For example:

```;----------------------------------------------------------
; Activity: Recursive Functions, Part II
; Date: February 4, 2016.
; Authors:
;          A01166611 Pepper Pots
;          A01160611 Anthony Stark
;----------------------------------------------------------```

Due date is Thursday, February 4.

## Evaluation

This activity will be evaluated using the following criteria:

 -10 The program doesn't contain within comments the author's personal information. The program contains syntax errors. The program was plagiarized. Depending on the amount of exercises that were solved correctly.