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

Recursive Functions

Objectives

During this activity, students should be able to:

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 merge returns the list that results from combining in ascending order all the elements contained in the two lists of numbers taken as arguments. The input lists should be in ascending order. For example:
    > recursion:merge([1, 4], [1, 2, 8]).
    [1, 1, 2, 4, 8]   
    > recursion:merge([], []).                          
    []   
    > recursion:merge([35, 62, 81, 90, 91], [3, 83, 85, 90]).  
    [3, 35, 62, 81, 83, 85, 90, 90, 91] 
    
  3. 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]
  4. 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([]).
    []
  5. 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 return a list with a sequence of ones and zeros equivalent to the binary representation of N. For example:
    > recursion:binary(0).           
    []   
    > recursion:binary(30).
    [1, 1, 1, 1, 0]  
    > recursion:binary(45123).
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1]
    
  6. 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"]
  7. 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).
    []
  8. 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]
  9. 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}]
  10. 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]

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 31, 2010.
%% Erlang Source File
%% Activity: Recursive Functions
%% Author: Steve Rogers, 449999

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

Due date: Tuesday, 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.
10 The program contains syntax errors.
DA The program was plagiarized.
10-100 Depending on the amount of exercises that were solved correctly.
© 1996-2010 by Ariel Ortiz (ariel.ortiz@itesm.mx)
Made with Django | Licensed under Creative Commons | Valid XHTML | Valid CSS