# Recursive Functions

## Objectives

During this activity, students should be able to:

• Write recursive using the Erlang programming language.

This activity helps the student 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 recursive programming exercises using Erlang. Place all your functions in a module called `recursion`.

NOTE: For this activity, you are not allowed to use any of the functions defined in Erlang's `lists` module.

1. The function `but_last` returns a list with the same elements as its input list but excluding the last element. Assume that the input list contains at least one element. For example:
```> recursion:but_last([a, b, c, d]).
[a,b,c]
> recursion:but_last([1]).
[]
> recursion:but_last([first, middle, last]).
[first,middle]```
2. The function `insert` takes two arguments: a number N and a list of numbers L in ascending order. It returns a new list with the same elements as L but inserting N in its corresponding place. For example:
```> recursion:insert(5, [1, 3, 6, 7, 9, 16]).
[1,3,5,6,7,9,16]
> recursion:insert(10, [1, 5, 6]).
[1,5,6,10]
> recursion:insert(14, []).
[14]```
3. The function `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 problem. For example:
```> recursion:sort([4, 3, 6, 8, 3, 0, 9, 1, 7]).
[0,1,3,3,4,6,7,8,9]
> recursion:sort([]).
[]```
4. The function `bcd` takes an integer N as input (assume that N ≥ 0), and returns a list of strings with the BCD representation of N. A BCD (Binary Coded Decimal) number is an encoding for decimal numbers in which each decimal digit is represented by its own 4-bit binary sequence. Examples:
```> recursion:bcd(27).
["0010","0111"]
> recursion:bcd(1093).
["0001","0000","1001","0011"]
> recursion:bcd(0).
["0000"]```
5. 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. Examples:
```> recursion:prime_factors(6).
[2,3]
> recursion:prime_factors(17).
[17]
> recursion:prime_factors(96).
[2,2,2,2,2,3]
> recursion:prime_factors(666).
[2,3,3,37]
> recursion:prime_factors(1).
[]```
6. 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. For example:
```> recursion:compress([a, a, a, a, b, c, c, a, a, d, e, e, e, e]).
[a,b,c,a,d,e]```
7. The function `encode` takes a list Lst as its argument. Consecutive duplicates of elements in Lst are encoded as tuples {N, E} where N is the number of duplicates of the element E. If an element has no duplicates, it is simply copied into the result list. For example:
```> recursion:encode([a, a, a, a, b, c, c, a, a, d, e, e, e, e]).
[{4,a},b,{2,c},{2,a},d,{4,e}]```
8. The function `decode` takes as its argument an encoded list Lst like the output from the previous problem. It returns the decoded version of Lst. For example:
```> recursion:decode([{4, a}, b, {2, c}, {2, a}, d, {4, e}]).
[a,a,a,a,b,c,c,a,a,d,e,e,e,e]```
9. The function `combinations` takes two arguments: a list Lst and a number N. It returns a list containing all possible combinations of size N taken from Lst (assume that 0 < N ≤ length(Lst)). For example:
```> recursion:combinations([a, b, c, d], 3).
[[a,b,c],[a,b,d],[a,c,d],[b,c,d]]
> recursion:combinations([january, february, march], 2).
[[january,february],[january,march],[february,march]]
> recursion:combinations([1, 2, 3], 1).
[[1],[2],[3]]
> recursion:combinations([1, 2, 3], 3).
[[1,2,3]]```
10. The function `permutations` takes two arguments: a list Lst and a number N. It returns a list containing all possible permutations of size N taken from Lst with no repetitions (assume that 0 < N ≤ length(Lst)). For example:
```> recursion:permutations([a, b, c, d], 3).
[[a,b,c],
[a,b,d],
[a,c,b],
[a,c,d],
[a,d,b],
[a,d,c],
[b,a,c],
[b,a,d],
[b,c,a],
[b,c,d],
[b,d,a],
[b,d,c],
[c,a,b],
[c,a,d],
[c,b,a],
[c,b,d],
[c,d,a],
[c,d,b],
[d,a,b],
[d,a,c],
[d,b,a],
[d,b,c],
[d,c,a],
[d,c,b]]
> recursion:permutations([january, february, march], 2).
[[january,february],
[january,march],
[february,january],
[february,march],
[march,january],
[march,february]]
> recursion:permutations([1, 2, 3], 1).
[[1],[2],[3]]
> recursion:permutations([1, 2, 3], 3).
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]```

## Deliverables

Using the Online Assignment Delivery System (SETA), deliver the file called `recursion.erl`. 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 25, 2008.
%% Erlang Source File
%% Activity: Recursive Functions
%% Author: Steve Rogers, 449999

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

Due date: Monday, August 25.

## 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.
© 1996-2008 by Ariel Ortiz (ariel.ortiz@itesm.mx)
ArielOrtiz.com | Made with Django | Licensed under Creative Commons | Valid XHTML | Valid CSS