REC - Recursive Searching and Sorting (Lesson)

APCompSci_LessonTopBanner.png

Recursive Searching and Sorting

Introduction

Sometimes a problem can be solved by solving smaller or simpler versions of the same problem rather than attempting an iterative solution. That is why we learned about recursion in our previous lesson. Can you think of any iterative algorithms that we have done so far that might work better recursively? Think about how we search or sort data…those tasks require a lot of repetition. Could they be done using recursion?

Merge Sort

Merge sort is a recursive sorting method. It uses the divide and conquer method that is like the divide and conquer method of a binary search. The merge sort splits an array in half repeatedly until it gets down to one element. It then merges the elements back together in order.

Let’s look at how the merge sort will sort the numbers 9, 0, 8, 3, 2, 1 in ascending order.

how the merge sort will sort numbers 9, 0, 8, 3, 2, 1 in ascending order 

Notice how the array of ints is split in half, then split in half again, etc. until it gets to one int. Then it is pieced back together, one portion at a time, in the correct order. The repetition in this sort is recursive. The merge sort can be used to sort arrays or ArrayLists.

The binary search is also an example of recursion. Recall that the binary search continually splits an array of data in half until the desired element is found. The repetition of splitting the array in half is done recursively.

Book Icon Click on "Runestone Academy" below to open the required reading that is listed.

Runestone Academy: AP CSA – Java Review Links to an external site.:

  • READ:
  • 13.3 – Binary Search
  • 13.6 – Merge Sort

Book Icon Click on "Introduction to Computer Science Using Java" below to open the required reading that is listed.

Introduction to Computer Science Using Java Links to an external site.:

  • READ:
  • Chapter 93: More Recursion
  • Chapter 94: Recursion with Strings
  • Complete the quiz for practice.

Book Icon 5 Steps to a 5:

  • READ:
  • Concept 12
  • Concept 13
  • Complete Practice Exams 1 & 2

Practice It

Recursion Exercises

You do not need to write Recursive methods on the AP Exam; however, it is good practice to try writing a few. Select a few of the following Pracitice It Exercises to practice writing recursion.

Practice Icon Practice-It! Practice

  • Go to the PracticeIt website Links to an external site..
  • Log into account.
  • Click on Start Practicing!
  • Go to the most recent edition.
  • Click on Chapter 12: Recursion

  • Complete Exercises: 12.1 – 12.3, 12.6 – 12.14, 12.18 – 12.22

Merge Sort Practice

Practice Icon Practice-It! Practice

Recursion Quiz Review

APCompSci_LessonBottomBanner.pngIMAGES CREATED BY GAVS