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

Individually, solve the following set of programming exercises using Clojure. Place all your functions in a name space called `recursion2`. 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

Using the Online Assignment Delivery System (SETA), deliver a single file called `recursion2.clj` containing your solutions and the unit tests. No assignments will be accepted through e-mail or any other means.

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

```
;;; ITESM CEM, August 31, 2012.
;;; Clojure Source File
;;; Activity: Recursive Functions, Part II
;;; Author: Steve Rogers, 1166611

.
. (The rest of the program goes here)
.```

Due date: Friday, August 31.

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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://arielortiz.info/apps/s201213/tc2006/activity_recursive_functions_part_2/", "fetch_time": 1717031856000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-22/segments/1715971059412.27/warc/CC-MAIN-20240529230852-20240530020852-00830.warc.gz", "warc_record_offset": 73087693, "warc_record_length": 4693, "token_count": 2705, "char_count": 8554, "score": 3.5625, "int_score": 4, "crawl": "CC-MAIN-2024-22", "snapshot_type": "latest", "language": "en", "language_score": 0.7397018074989319, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00024-of-00064.parquet"}