Lesson 9: Recursive Algorithms

We previously wrote an algorithm to determine if a word or phrase was a palindrome. We also learned in the previous lesson that any iterative solution can be translated to a recursive solution.

Discuss: Use the Retrieve-Pair-Share strategy to discuss the prompt.

• How could we solve this problem recursively?

Discussion Goal: Students share that they can translate the iterative solution to a recursive solution by identifying the base and recursive case. Students realize that the base case is when there is either one letter or no letters left. The recursive case is to compare the first and last letter of the word, then remove them to examine the next letters.

Do This: Click through the animated slide to identify the base and recursive cases for a recursive palindrome solution.

You saw in the previous lesson that you could write recursive algorithms to work with arrays. Since a recursive algorithm can work anywhere that an iterative algorithm can, we can also write recursive solutions to work with other types of data, including Strings.

Do This: Review the lesson objectives.

Group: Place students in pairs.

Do This: Direct students to Level 1 on Code Studio to investigate the program with a partner. Students make the changes to the program as prompted.

Discuss: Click through the animated slide to display the prompts.

• What do you notice about the code in this program?
• What do you wonder about the code in this program?

Discussion Goal: Students notice that the recursive solution has the same results as the iterative solution. Students may also notice that the recursive solution is easier to read and identify the base and recursive cases in both solutions. Students may wonder if one approach is faster or why they might choose one approach over another.

Remind students that iterative and recursive solutions can be used interchangeably and that there are benefits to both approaches to solving problems.

Display: Show the video – Recursion.

Distribute: Give each student a copy of the Tracing Recursion handout.

Do This: Direct students to complete Levels 2 and 3 on Code Studio. On Level 2, students complete a choice level tracing recursive methods with Strings, arrays, or ArrayLists and complete the Tracing Recursion handout. Students continue to complete a Check for Understanding on Level 3.

Before working towards the next benchmark, it is helpful to assess your achievement of this benchmark and get feedback on your development so far.

Do This: Click through the animated slide to have students participate in the Code Review Call and Response.

Do This: Direct students to complete a code review on Level 4.

We just learned a lot of new information today, which may have even answered some of the Need to Know questions you wrote down about the Creative Coding Project. As we progress through the unit, it is helpful to stop and note what we have learned that is related to or useful for the project.

Do This: Have students review the questions they wrote in the "Need to Know" column on page two of their Creative Coding with The Theater Project Planning Guide. Students add new questions to this column, check off any answered questions, and write answers to any questions in the "Learned" column.

Do This: Have students share what they added to their chart with a partner.

If time permits, you can also have students share as a class.

Do This: Review the concepts covered in this lesson.

Check For Understanding Question(s) and solutions can be found in each lesson on Code Studio. These questions can be used for an exit ticket.

To assign questions from the AP Classroom Question Bank that align with this lesson, create a custom quiz in AP Classroom by searching the Question Bank for the Essential Knowledge statements listed at the top of this lesson plan. You can find instructions and video demonstrations to do this on AP Central.