Bev Facey Community High

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.

• Prerequisites: CSE3110: Iterative Algorithm 1, CSE3120: Object-oriented Programming 1

Theory

1. 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

2. 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

1. create and/or modify recursive algorithms to solve problems

   • demonstrate the use of appropriate general design techniques to draft algorithms that use recursion
   • analyze and decompose the problem into appropriate subsections using the decomposition techniques appropriate for the chosen design approach
   • evaluate subsections and identify any that may require a recursive approach
   • identify which recursive algorithms are appropriate
   • sequence the various subsections appropriately
   • test and modify the developing algorithm with appropriate data using a “fail-on-paper” process

2. create and/or modify programs that use recursion

   • convert algorithms calling for recursive structures into programs that reflect the algorithm’s design
   • use original (user-created) or pre-existing recursive merge and/or sort algorithms appropriate to the data being manipulated
   • utilize the appropriate operators, methods, functions or procedures required to carry out the recursive algorithms
   • use internal and external documentation

3. compare program operation and outcomes with the intent of the algorithm and modify, as required

   • use appropriate error-trapping mechanisms built into the programming environment, as well as programmer-directed error-trapping techniques, to eliminate logic errors and debug the program
   • compare the congruency between the outcomes of the debugged program and the original intent of the algorithm and modify both, as required

This site is open source. Improve this page.