Scribd
Upload
2 views2 pages

ASSIGNMENT02 Recursion

The document outlines an assignment for 2nd year engineering students at the University of Blida 1, focusing on recursion in algorithmics and data structures. It includes multiple exercises requiring the implementation of recursive functions for tasks such as removing duplicates from a list, inserting elements into a sorted list, and checking for palindromes. Additionally, it asks for iterative solutions to certain problems, emphasizing both recursive and iterative approaches to problem-solving in computer science.

Uploaded by

Naoufel Ben
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views2 pages

ASSIGNMENT02 Recursion

The document outlines an assignment for 2nd year engineering students at the University of Blida 1, focusing on recursion in algorithmics and data structures. It includes multiple exercises requiring the implementation of recursive functions for tasks such as removing duplicates from a list, inserting elements into a sorted list, and checking for palindromes. Additionally, it asks for iterative solutions to certain problems, emphasizing both recursive and iterative approaches to problem-solving in computer science.

Uploaded by

Naoufel Ben
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

University of Blida 1 ALGORITHMICS AND DATA 2nd year of engineering

Computer Science department STRUCTURES Academic Year 2024/2025

ASSIGNEMENT N°2 : RECURSION

EXERCISE 1
Q1. Write a recursive function removeDuplicate(L:List) :List that removes duplicates from a
sorted list L. Given the list [3, 3, 6, 9, 9, 9, 9, 11], the function returns [3, 6, 9, 11].
Q2. Write a recursive function insert(L:List, X :Integer) :List that inserts an integer X into a
sorted list L. Given the list [3, 3, 6, 9, 9, 11] and X=7, the function returns [3, 3, 6, 7, 9, 9, 11].

EXERCISE 2
Q1. Write a recursive function sumArray(A : Array of Integer, n : Integer) : Integer that
computes the sum of the elements in an array.
Q2. Write a recursive function maxArray(A : Array of Integer, n : Integer) : Integer that
returns the index of the highest value in A.
Q3. Write a recursive function isSorted(A : Array of Integer, n : Integer) : Boolean that checks
whether the array A is sorted.
Q4. Write a recursive procedure reverseArray(Var A : Array of Integer, n : Integer) that
reverses the order of the elements in A.
Q5. Write a recursive function trans(A: Matrix of Integers, n : Integer) : Matrix of Integers
that transforms a square matrix 𝐴 ∈ ℤ𝑛×𝑛 into its transpose 𝐴𝑇 . It is assumed that 𝑛 is an
exact power of 2. The function should implement the "Divide and Conquer" principle. Given
a square matrix A, the function divides A into 4 sub-matrices:

In this case, the transpose of A is given by:

1/2
University of Blida 1 ALGORITHMICS AND DATA 2nd year of engineering
Computer Science department STRUCTURES Academic Year 2024/2025

EXERCISE 3
Consider a nonnegative integer 𝑛 whose digits always appear in ascending order from left
to right, such as 24667. In other words, if 𝑑𝑚−1 ⋯ 𝑑1 𝑑0 represents the sequence of 𝑚 digits of
n, then 𝑑𝑖 ≤ 𝑑𝑗 for 𝑖 < 𝑗. Given an additional digit 0 < 𝑥 ≤ 9, write a recursive function that
returns the integer that results from inserting 𝑥 in 𝑛, such that its digits also appear in ascending
order from left to right. For instance, if 𝑛 = 24667 and 𝑥 = 5, the function should return
245667.

EXERCISE 4
Q1. A palindrome is a word that reads the same way from left to right or from right to left,
for example, ABBA, ELLE. Write a recursive function that determines if a word is a
palindrome.
Q2. Given a string of characters, the problem of the longest palindrome consists of
determining the longest substring that is a palindrome. For example, if s=ABCHHCCA, the
function returns: CHHC. Write a recursive function that extracts the longest palindrome
substring.

EXERCISE 5

Propose iterative solutions for the following functions:


Q1. Exercise 3,
Q2. Extraction of the longest palindrome substring (Q2 of Exercise 4),
Q3. Swamp traversal (Course example).

2/2

You might also like