Description

We call recursive algorithms the class of What is procedure repeatedly over the object of
algorithms that we use the same the algorithm until, for some reason, we
recursion? stop repetitions and solve it in a
different way.
However, the idea of recursion is much more widely applied, as in mathematics, and even philosophy. As such, we will A mathematical paradigm. introduce recursion with:
A philosophical tool. ● the concept of recursion;
● recursive equation and stopping condition.
CSC 6013 – Week 4

What is recursion in CS
● A recursive equation, a relation, or set of relations that establishes the answer you are looking for to an instance n by calling itself to a different instance; ○ in this case:
■ the answer for n is the same as the answer for n-1;
● A stopping condition that delivers the A recursive algorithm needs: answer for a specific value or set of values;
● one or more recursive ○ in this case: equations; ■ it returns True for n equal to 1 or
● one or more stop conditions. ■ it returns False for n smaller than or equal to 0.
Video: What on Earth is Recursion?.
We call recursive algorithms the class of What is procedure repeatedly over the object of
algorithms that we use the same the algorithm until, for some reason, we
recursion? stop repetitions and solve it in a
different way.
However, the idea of recursion is much more widely applied, as in mathematics, and even philosophy. As such, we will A mathematical paradigm. introduce recursion with:
A philosophical tool. ● the concept of recursion;
● recursive equation and stopping condition.
CSC 6013 – Week 4

Classic Recursion
Computing the n-th term of the Fibonacci Sequence Recursively
The recursive implementation is easy to understand because it is similar to the problem definition.
● We can define the n-th term of the Fibonacci sequence as:
○ 1 for the first two terms;
○ the sum of the (n-1)-th and (n-2)-th terms.
● The stopping condition is:
○ Fibonacci sequence term n is equal to 1 for the n equal to 1 or 2; ● The recursive equation is:
○ Fibonacci sequence term n is equal to the sum of Fibonacci sequence term n-1 and Fibonacci sequence term n-2.
Video: Recursion Simply Explained.

Example 1 – Depth First Search in Graphs
● The recursive implementation of this algorithm uses:
○ an array V with all vertices vi holding information if they are visited or not;
○ an adjacency list of edges E with
triplets (vi , vj , 1)
○ a counter count to keep the track of the nodes to visit.
There is another non recursive implementation to the DFS algorithm that uses a stack similarly to the BFS algorithm seen the previous week that uses a queue.
While DFS is naturally recursive, BFS is naturally iterative.

Third Coding Project – P#4
1. Adapt the Binary Search algorithm seem in class to search a given element assuming that the array is not in ascending order, but instead it is sorted in descending order. Trace your algorithm execution printing:
a. at each recursive call, print the subarray from start to end and show the mid element.
b. test your algorithm for the arrays:
i. A1 = [99, 67, 56, 51, 44, 39, 38, 23, 21, 17, 11, 2] searching for 44;
ii. A1 = [99, 67, 56, 51, 44, 39, 38, 23, 21, 17, 11, 2] searching for 56;
iii. A1 = [99, 67, 56, 51, 44, 39, 38, 23, 21, 17, 11, 2] searching for 42; iv. A2 = [9, 7, 6, 4, 2, 0, -1, -3, -5, -8, -9] searching for -1;
v. A2 = [9, 7, 6, 4, 2, 0, -1, -3, -5, -8, -9] searching for -7.
To both programs you have to submit the code (.py file) of your adapted algorithm and a .pdf with the test cases outputs.
Two algorithms to adapt, this is the first.
Third Coding Project – P#4
2. Adapt the Maximum Element in an Array algorithm seem to search for the minimum element in the array. Trace your algorithm execution printing:
a. at the beginning of each recursive call the start and end values.
b. at the returning of each recursive call the returned value (the minimum of the array slice).
c. test your algorithm for the arrays:
i. A3 = [44, 63, 77, 17, 20, 99, 84, 6, 39, 52]
ii. A4 = [52, 84, 6, 39, 20, 77, 17, 99, 44, 63]
iii. A5 = [6, 17, 20, 39, 44, 52, 63, 77, 84, 99]
Your task:
Fourth Quiz – Q#4
● The fourth quiz in this course covers the topics of Week 4;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 4), and it is not a timed quiz:
○ You can take as long as you want to answer it (a quiz taken in less than one hour is usually a too short time);
● The quiz is open book, open notes, and you can even use any language Interpreter to answer it;
● Yet, the quiz is evaluated and you are allowed to submit it only once.
Your task: