Chapter 12: Recursion 223
Chapter 12: Recursion
Lab Exercises
Topics Lab Exercises
Basic Recursion Computing Powers
Counting and Summing Digits
Base Conversion
Efficient Computation of Fibonacci Numbers
Fractals Sierpinski Triangles
Modifying the Koch Snowflake
Computing Powers
Computing a positive integer power of a number is easily seen as a recursive process. Consider an:
File Power.java contains a main program that reads in integers base and exp and calls method power to
compute baseexp. Fill in the code for power to make it a recursive method to do the power computation. The
comments provide guidance.
// *****************************************************************
import java.util.Scanner;
public class Power
{
public static void main(String[] args)
{
System.out.print(“Welcome to the power program! “);
System.out.println(“Please use integers only.”);
// ———————————————-
public static int power(int base, int exp)
{
int pow;
//if the exponent is 0, set pow to 1
//otherwise set pow to base*base^(exp-1)
Chapter 12: Recursion 225
Counting and Summing Digits
The problem of counting the digits in a positive integer or summing those digits can be solved recursively. For
example, to count the number of digits think as follows:
If the integer is less than 10 there is only one digit (the base case).
The following is the recursive algorithm implemented in Java.
public int numDigits (int num)
{
if (num < 10)
return (1); //a number < 10 has only one digit
else
return (1 + numDigits (num / 10));
}
1. Add a static method named sumDigits that finds the sum of the digits in a positive integer. Also add code to
2. Most identification numbers, such as the ISBN number on books or the Universal Product Code (UPC) on
grocery products or the identification number on a traveller’s check, have at least one digit in the number that
is a check digit. The check digit is used to detect errors in the number. The simplest check digit scheme is to
add one digit to the identification number so that the sum of all the digits, including the check digit, is evenly
divisible by some particular integer. For example, American Express Traveller’s checks add a check digit so
88231256 — ok
3180012 — error
226 Chapter 12: Recursion
// ******************************************************************
// DigitPlay.java
//
if (num <= 0)
System.out.println ( num + ” isn’t positive — start over!!”);
else
{
// Call numDigits to find the number of digits in the number
// Print the number returned from numDigits
return (1 + numDigits (num/10));
}
}
Base Conversion
One algorithm for converting a base 10 number to base b involves repeated division by the base b. Initially one
divides the number by b. The remainder from this division is the units digit (the rightmost digit) in the base b
1/4 = 0 1
The answer is read bottom to top in the remainder column, so 30 (base 10) = 132 (base 4).
Think about how this is recursive in nature: If you want to convert x (30 in our example) to base b (4 in our
example), the rightmost digit is the remainder x % b. To get the rest of the digits, you perform the same process
on what is left; that is, you convert the quotient x / b to base b. If x / b is 0, there is no rest; x is a single base b
if ( ____________________________________ ) //fill in base case
{
return (“” + ______________________________ );
}
else
{
// Recursive step: the number is the base b representation of
// the quotient concatenated with the remainder
228 Chapter 12: Recursion
Number: 347 Base: 5 ––> should print 2342
Number: 3289 Base: 8 —> should print 6331
Improving the program: Currently the program doesn’t print the correct digits for bases greater than 10. Add
code to your convert method so the digits are correct for bases up to and including 16.
// *****************************************************************
// BaseConversion.java
//
// Recursively converts an integer from base 10 to another base
// *****************************************************************
System.out.print (“Enter the base: “);
base = scan.nextInt();
// Call convert and print the answer
}
// ————————————————-
// Converts a base 10 number to another base.
Efficient Computation of Fibonacci Numbers
The Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two
previous terms. More specifically, if fib(n) is the nth term of the sequence, then the sequence can be defined as
follows:
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) n>1
1. Because the Fibonacci sequence is defined recursively, it is natural to write a recursive method to
2. File TestFib.java contains a simple driver that asks the user for an integer and uses the fib1 method to
compute that element in the Fibonacci sequence. Save this file to your directory and use it to test your fib1
method. First try small integers, then larger ones. You’ll notice that the number doesn’t have to get very big
before the calculation takes a very long time. The problem is that the fib1 method is making lots and lots of
recursive calls. To see this, add a print statement at the beginning of your fib1 method that indicates what
3. The fundamental source of the inefficiency is not the fact that recursive calls are being made, but that
values are being recomputed. One way around this is to compute the values from the beginning of the
sequence instead of from the end, saving them in an array as you go. Although this could be done
recursively, it is more natural to do it iteratively. Proceed as follows:
a. Add a method fib2 to your Fib class. Like fib1, fib2 should be static and should take an integer and
//
// A utility class that provide methods to compute elements of the
// Fibonacci sequence.
// *******************************************************************
public class Fib
{
//——————————————————————
230 Chapter 12: Recursion
// *******************************************************************
// TestFib.java
//
// A simple driver that uses the Fib class to compute the
// nth element of the Fibonacci sequence.
// *******************************************************************
import java.util.Scanner;
public class TestFib
{
public static void main(String[] args)
{
int n, fib;
Palindromes
A palindrome is a string that is the same forward and backward. In Chapter 5 you saw a program that uses a
loop to determine whether a string is a palindrome. However, it is also easy to define a palindrome recursively
as follows:
A string containing fewer than 2 letters is always a palindrome.
A string containing 2 or more letters is a palindrome if
its first and last letters are the same, and
the rest of the string (without the first and last letters) is also a palindrome.
Write a program that prompts for and reads in a string, then prints a message saying whether it is a palindrome.
Printing a String Backwards
Printing a string backwards can be done iteratively or recursively. To do it recursively, think of the following
specification:
If s contains any characters (i.e., is not the empty string)
print the last character in s
print s’ backwards, where s’ is s without its last character
File Backwards.java contains a program that prompts the user for a string, then calls method printBackwards to
//————————————————————–
public static void main(String[] args)
{
String msg;
Scanner scan = new Scanner(System.in);
System.out.print(“Enter a string: “);
Recursive Linear Search
File IntegerListS.java contains a class IntegerListS that represents a list of integers (you may have used a
version of this in an earlier lab); IntegerListSTest.java contains a simple menu-driven test program that lets the
user create, sort, and print a list and search for an element using a linear search.
Many list processing tasks, including searching, can be done recursively. The base case typically involves doing
top-level search routine (linearSearchRec), which just needs the thing to look for.
Now change IntegerListTest.java so that it calls linearSearchRec instead of linearSearch when the user asks for
a linear search. Thoroughly test the program.
// ***************************************************************
// IntegerListS.java
//
{
list = new int[size];
}
// ————————————————————-
// Fills the array with integers between 1 and 100, inclusive
// ————————————————————-
public void randomize()
{
{
// Returns the index of the first occurrence of target in the list.
// Returns -1 if target does not appear in the list.
// ——————————————————————
public int linearSearch(int target)
{
int location = -1;
}
// ——————————————————————
// Recursive implementation of the linear search – searches
// for target starting at index lo.
// ——————————————————————
private int linearSearchR (int target, int lo)
{
if (list[j] < list[minIndex])
minIndex = j;
//swap list[i] with smallest element
int temp = list[i];
list[i] = list[minIndex];
Chapter 12: Recursion 235
static Scanner scan = new Scanner(System.in);
// ——————————————————————
// Creates a list, then repeatedly print the menu and do what the
// user asks until they quit.
// ——————————————————————
{
case 0:
case 1:
System.out.println(“How big should the list be?”);
case 2:
case 3:
System.out.print(“Enter the value to look for: “);
case 4:
list.print();
236 Chapter 12: Recursion
break;
default:
System.out.println(“Sorry, invalid choice”)
}
}
// ————————————-
// Prints the menu of user’s choices.
// ————————————-
public static void printMenu()
{
System.out.println(“\n Menu “);
System.out.println(” ====”);
System.out.println(“0: Quit”);
}
Chapter 12: Recursion 237
Recursive Binary Search
The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered list. The
algorithm (in pseudocode) is as follows:
highIndex – the maximum index of the part of the list being searched
lowIndex – the minimum index of the part of the list being searched
target — the item being searched for
//look in the middle
else
search the second half of the list
Notice the recursive nature of the algorithm. It is easily implemented recursively. Note that three parameters are
needed—the target and the indices of the first and last elements in the part of the list to be searched. To “search
the first half of the list” the algorithm must be called with the high and low index parameters representing the
first half of the list. Similarly, to search the second half the algorithm must be called with the high and low
index parameters representing the second half of the list. The file IntegerListB.java contains a class representing
a list of integers (the same class that has been used in a few other labs); the file IntegerListBTest.java contains a
simple menu-driven test program that lets the user create, sort, and print a list and search for an item in the list
using a linear search or a binary search. Your job is to complete the binary search algorithm (method
binarySearchR). The basic algorithm is given above but it leaves out one thing: what happens if the target is not
in the list? What condition will let the program know that the target has not been found? If the low and high
indices are changed each time so that the middle item is NOT examined again (see the diagram of indices
below) then the list is guaranteed to shrink each time and the indices “cross”—that is, the high index becomes
less than the low index. That is the condition that indicates the target was not found.
lo middle high
Fill in the blanks below, then type your code in. Remember when you test the search to first sort the list.
private int binarySearchR (int target, int lo, int hi)
{
int index;
index = mid;
else if (target < list[mid])
// fill in the recursive call to search the first half