Overview

In this reading/viewing we will have a look at a programming technique known as recursion. At its simplest, recursion is just when a method calls itself. However, at its heart recursion is a powerful problem solving strategy that involves decomposing a problem into smaller versions of the same problem.

To start we’ll look at the essential components of a recursive algorithm/method and see a couple of classic examples involving recursion. Recursion will seem a bit mystical at first; with repeated application it will become another wonderful tool in our programming toolbox.

Required Reading / Viewing

• Learning Java: Part 24: Recursion and the Fibonacci Sequence (YouTube)
• What on Earth is Recursion? (YouTube)
• Java Recursion. Read up to (but not including) the section on Towers of Hanoi.

Learning Objectives

BASIC Learning Objectives

Each student will be responsible for learning and demonstrating proficiency in the following objectives PRIOR to the class meeting. The reading quiz will test these objectives.

1. Compare and contrast the long and int types in Java.
2. Describe the roles of the base case and recursive case in a recursive method.
3. Given a recursive method, identify the base case(s) and the recursive case(s).

ADVANCED Learning Objectives

The following objectives should be mastered by each student DURING and FOLLOWING the class session through active work and practice.

1. Write, read, and trace Java code that involves recursion.
2. Compare and contrast loops and recursion.

Pre-class Exercises

These exercises are geared towards mastering the BASIC learning objectives listed above. You are expected to submit them before class and it is highly recommended that you complete them before attempting the reading quiz.

1. In your own words, describe why a base case is required in an recursive method.

2. Consider the following recursive method:

   public static int foo(int x)
   {
       if (x == 1)
           return 1;
       else { 
           return foo(x-1) + 1;
       }
   }

   Part A: What is the base case(s)?

   Part B: What is the recursive case(s)?

   Part C: Assuming that we call foo(10) from a main method, what is the most number of items on the call stack when executing the code? Hint: Review section 12.3.2 for a refresher on the call stack.