Recursion
Recursion is an important and powerful programming tool. At times, it can be the only way to elegantly solve a particular programming problem. But it is also a hard concept to wrap your head around.
Today’s lab introduces you to recursion. The written portion uses multiple simple examples to illustrate the concept, and provides an opportunity to compare recursive and iterative solutions. A big part of learning how to use recursion is learning when not to use it. The programming component provides an opportunity to complete several simple recursive functions on a small and useful graph.
1. Written Exercises (60 Minutes)
As usual, we begin with a written lab component. Please complete these exercises carefully. Your course staff will review and discuss your answers along with the rest of your section.
Complete this part of the lab in pairs using Google Docs. Create a copy of our document template, and then edit it to record you and your partner’s answers. Note that you must open this document using your @illinois.edu Google Apps account. We will not grant access to non-Illinois users.
Have a course staff member check your answers as you go. When you are done, move on to the programming component.
2. Practice With Recursion (50 Minutes)
Recursion is hard to get started with, but it gets easier with practice—like everything else you do as a programmer. In the second half of the lab we’ll provide you with some practice at implementing several recursive functions. We’ll do this in the context of trees one of the more useful and interesting computer science data structures.
2.1. Forking and Cloning the Lab9 IntelliJ Project
We’ve set up an Lab 9 GitHub repository containing an IntelliJ Project that’s correctly configured for Lab 9. Getting access to it is similar to how you imported MP0. But you have to fork our repository first. If it’s not obvious how to do that, try following these instructions.
Note that we return (again) to IntelliJ for Lab 9. Please don’t try and complete the programming portion using Android Studio.
2.2. Your Goal
Your goal today is to complete the EmployeeDatabase.java class.
There are some simple checkstyle errors to fix, but your main objective is to
complete two simple functions: one that counts up from a given employee, the
other that counts down.
As usual, you may find the official
Lab9 documentation helpful.
In both cases you are encouraged to complete both an iterative and recursive solution to get a feeling for the design trade-offs involved. When you are done, you may want to compare with another group, and discuss the iterative-recursive trade-offs with them. Do they feel the same way about their implementations as you do?