CSE 3310: Recursive Algorithms 1
Students learn how to use a new program control flow mechanism called recursion. They then use this mechanism to write a number of basic recursive algorithms and programs such as a recursive version of the binary search, the quicksort and the merge sort.
Theory
-
analyze and represent the nature and utility of the recursive functions or procedures
- explain and represent the key features of recursive algorithms including:
- illustrate how recursive algorithms define themselves in terms of themselves
- illustrate the use and purpose of the base case in recursion
- describe and represent the “divide and conquer” approach to creating recursive algorithms
- describe and represent the interchangeability of recursive and iterative operations
- compare and contrast recursion and iteration highlighting:
- programmer efficiency
- space efficiency
- time efficiency
- outline the importance of recursion in creating dynamic data structures
- compare and contrast tail end and head end recursion
- explain and represent how the system stack (or equivalent structure) is used to carry out recursive operations
-
analyze and represent the nature, structure and utility of recursive search and sort algorithms
- describe at least four recursive algorithms used in dynamic data manipulation
- compare and contrast iterative and recursive approaches to binary searching by:
- describing and representing iterative and recursive binary search algorithms
- explaining the advantages and disadvantages of iterative and recursive approaches to binary searching
- compare and contrast at least two recursive sorts by:
- describing and representing the quicksort and the merge sort
- describing and representing the heapsort
- explaining the advantages and disadvantages of the quicksort, merge sort and heapsort
Coding
All of the following assignments may be done in a language of your choice. Submit all relevant program files for these 4 assignments.
- Design and write an algorithm that uses recursion to return a given number’s prime factorization.
- Prime factorization refers to the process of factoring a number until you have a list of only prime numbers which, when multiplied together, equals the starting number.
- E.g. 12 = 2 x 2 x 3, 42 = 2 x 3 x 7
- Design and write an algorithm that uses recursion to calculate the Fibonacci sequence up to a given number, or up to a certain number of terms.
- You can read more about the Fibonacci sequence here.
- Design and write an algorithm that uses recursion to return a list/array of every permutation of an inputted string.
- A permutation is an ordered subset of a set. For example, when considering the set of all the letters in the alphabet, (A, B, C) is a different permutation than (B, A, C) despite containing the same letters.
- Design and write an algorithm that uses merge sort (or some other sorting method that involves recursion) to sort an object by the values of its attributes. This algorithm must include the following considerations:
- The object must be created by you, either for this task or for a previous task.
- You don’t have to incorporate every attribute of the object into your sorting method, but it must consider more than 1 attribute.