UNI. OF L'POOL

INTRODUCTION TO PROGRAMMING IN JAVA: REPETITION (RECURSION)


CONTENTS

1. Overview
1.1.Summary
2. Example problem - Decimal to binary conversion
2.1. Requirements
2.2. Analysis
 
2.3. Design
2.4. Implementation
2.5. Testing
3. Decimal to hexadecimal conversion
4. Alternative (recursive) implementation of Fibonacci Problem

The decimal to binary conversion example contains makes use of a default constructor, i.e. one that is not explicitly defined.




1. OVERVIEW

Recursion is a mechanism whereby repetition can be achieved using (at its simplest) a method that continues to call itself until some terminating value is reached, i.e. without using some specific repetition construct. The flow of control in recursion can be conceptualised as shown in the Activity Diagram given in Figure 1 (corresponding Nassi-Shneiderman chart in Figure 2). Not that, in Figure 1, the method call is a call to the same method as the calling method.

RECURSION NS

Figure 2: NS chart indicating a recursive method

 
RECURSION AD SIMPLE

Figure 1: Recursion Activity Diagram (1)

Base case: The Boolean test at which the recursion ceases to "wind up" and starts to "unwind".
Recursive step: A method call which causes the recursion to "repeat" on each successive iteration (unless the base case is reached).
RECURSIVE FLOW OF CONTROL

Figure 3: Recursive flow of control

The actual flow of control should therefore more accurately be described as shown in Figure 3. The Figure shows a recursive loop that iterates 4 times, i.e. the Boolean test is invoked on four occasions. The hrad (red) line marked with arrows shows the flow of control as the recursion winds up, i.e. until such a point is reached where the iterative process stops at which point the recursion is said to unwind --- the dashed (purple) line in the Figure. The light (Greyed out) processes and control flow lines show processes that are not invoked and lines that are not "exercised" in this case.

The number of recursive iterations depends on the nature of the input to the Boolean test, i.e. anything between 0 (no iterations) and an infinite (never ending) loop. Consequently the approach to indicating the flow of control in recursion as shown in Figure 3 is not a good one --- we usually do not know in advance how many recursive iterations there will be. Consequently it is more convenient to indicate recursive flow of control as shown in Figure 4. Note in the figure that we have introduced some terminology specific to recursion:

 
RECURSION AD COMPLEX

Figure 4: Recursion Activity Digarms (2)

Although Figure 4 is more succinct than Figure 3 the flow of control is not immediately obvious in all cases. It is clear that if the base case is reached immediately there is no recursive step and flow of control passes down the left hand path to the "sink". However, if the base case is reached after N iterations flow of control will initially again pass down the left hand branch but this time round to return to the recursive step. Flow of control will then loop for N iterations as the recursion unwinds (the purple line in Figure 4) until the recursion is fully unwound when flow of control will again pass on to "end".

NS CHART DEPICTING RECURSIVE METHOD WITH STATEMENTS PENDING

Figure 6: NS chart depicting recursive method with statements pending

 

This process is made even more confusing (at least to the novice) when the recursion includes statements to be executed before the recursive step, i.e. statement to be executed as the recursion winds up; and further statements pending to be executed as the recursion unwinds. The effect of this can best be visualised by returning to a AD of the form shown in Figure 3. This is presented in Figure 5. From this Figure we can clearly see that the statements pending will not be invoked until the recursion starts to unwind. For completeness, Figure 6 gives a NS chart depicting a recursive method with statements pending.

RECURSIVE FLOW OF CONTROL WITH STATEMENTS PENDING

Figure 5: Recursive Flow of Control with statements pending



1.1 Summary

Recursion is a process whereby a method calls itself so as to achieve repetitious behaviour.
A recursive method comprises:
  1. A base case where the recursion stops and begins to unwind, and
  2. A recursive step where the method calls itself.
We say that a recursive algorithm winds up until the base case is reached and then unwinds.
 
During the unwinding process further program statements "pending" may be called.

Note also that what has been described above is the simplest form of recursion over forms include "double recursion" (two recursive steps one pending), and "nested recursion" (one recursive step nested within another).



2. EXAMPLE PROBLEM - DECIMAL TO BINARY CONVERSION


2.1 Requirements

Develop and implement some Java software which, when given a "base 10" (decimal) natural number, will convert this number into a binary number ("base 2"). For example, given the number 41 we would expect the system to output:

00000000 00000000 00000000 00101001

The standard mechanism, for converting from decimal to binary is to repeatedly divide the decimal number by 2 and, at each division, output the remainder (0 or 1). An example is given in Figure 7 where the binary number 101001 is derived from the decimal number 41.

Figure 7: Decimal to binary conversion.

Note: A Natural number is an integer greater than or equal to zero.


2.2 Analysis

A class diagram for the proposed solution is given in Figure 8. Because decimal to binary conversion is something we may want to do more often, the conversion routine has been designed as a stand alone class which must be interacted with using an application program. Note that the default constructor is used.

Figure 8: Class diagarm for decimal to binary conversion problem.



2.3 Design

2.3.1 Dec2Bin Class


Method Summary
public void convertDec2Bin(int decimalNumber, int digitCounter)
           Instance method to carry out conversion operating in a recursive manner. Method continues to recur until the given decimal number is 0, this is the base case at which point a call to the padWithZeroes method is made. As the recursion unwinds, on each iteration an appropriate digit ("0" or "1") is output.
private double padWithZeroes(int digitCounter)
           Instance method. Loops for 32-digitCounter iterations outputting a "0" on each iteration. On every eighth bit a space is output to separate the bytes making up a 32 bit integer.

An appropriate Nassi Shneiderman design for the above is given in Figure 9. Thus in this design we have used a recursive algorithm to ensure that the binary digits are output in the correct order. If we used a simple while loop the reverse result would be produced. To avoid this we would require a temporary storage structure in which to store the digits which can then be output in reverse. The latter approach would require extra work, and consequently the recursive approach is more efficient.

NASSI_SHNEIDERMAN CHART FOR DEC2BIN CLASS

Figure 9: Nassi-Shneiderman charts for Dec2Bin class methods


2.3.2 Dec2BinApp Class

Field Summary
private static Scanner keyboardInput
           A class instance to facilitate input from the input stream.

Method Summary
public static void main(String[] args)
           Main method. Calls inputNatNum the result of which is then used to create an instance of the class Dec2Bin using the default constructor, and then calls the convertDec2Bin method in the Dec2Bin class to carry out and output the conversion.
private static int inputNatNum()
           Class method to allow a user to input a natural number. Includes error checking and recovery facility.

An appropriate Nassi Shneiderman design for the above is given in Figure 10, and a Activity Diagram indicating the overall flow of control through the proposed software system in Figure 11. In Figure 11 flow of control enters at the top (the riser) and loops round between the base case and the recursive step until the base case is reached. The recursion is now fully "wound up". On reaching the base case control flow continues in the bottom-left loop, and when this loop is complete the recusion starts "to unwind". The latter is indicted by the bottom-right loop.

NASSI_SHNEIDERMAN CHART FOR DEC2BINAPP CLASS

Figure 10: Nassi-Shneiderman chart for Dec2BinApp class

FLOW CHART

Figure 11: Activity Diagarm for decimal to binary conversion software system.


2.4. Implementation

The encoding of the above design is given in Tables 1 and 2. Note that, in Table 1, we increment the digit counter using the arithmetic expression digitCounter+1 so that on the next recursion the digitCounter formal parameter is incremented by 1. If we had used the ++ incrementation operator (i.e. digitCounter++) this would have incremented the current formal parameter first and then passed this on as the formal parameter for the next recusive call of the convertDec2Bin method. As a result, when the recusion unwinds the digitCounter%8 == 0 test will nolonger operate in the desired manner and consequently white space will be output in an inappropraite manner.

// DECIMAL 2 BINARY
// Frans Coenen
// 30 may 1999
// Dept Computer Science, University of Liverpool

class Dec2Bin {

    // ------------------ METHODS ------------------------

    /* ------ CONVERT DECIMAL 2 BINARY */

    // Output digits and spaces between bytes when appropriate

    public void convertDec2Bin(int decimalNumber, int digitCounter) {
    
	// Base case 
	if (decimalNumber == 0) padWithZeros(digitCounter);
	 
        // Recursive step	
        else {     
            convertDec2Bin(decimalNumber/2,digitCounter+1);
            System.out.print(decimalNumber%2);
	    if (digitCounter%8 == 0) System.out.print(" ");
            }   
        }

    /* ------ PAD WITH ZEROS ------ */

    // Private class method to output a sequence of `0' characters to 
    // pad the output with, where the decimal number does not require 
    // all the 32 digits for its binary equivalent encoding. 

    private static void padWithZeros(int digitCounter) {
        final int TOTAL_DIGITS = 32;
	int loopParameter;
        int endValue = TOTAL_DIGITS-digitCounter;

        // For loop, output a `0' on each iteration
        for(loopParameter=1;loopParameter<=endValue;loopParameter++) {
            System.out.print("0");
            if (loopParameter%8 == 0) System.out.print(" ");
            }   
        }
    }

Table 1: Implementation for Dec2Bin class

// DECIMAL 2 BINARY APPLICATION
// Frans Coenen
// 30 May 1999
// Revised: Friday 26 August 2005
// Dept Computer Science, University of Liverpool

import java.util.*;

class Dec2BinApp{

    // ------------------- FIELDS ------------------------ 
                                           
    // Create Scanner class instance
    public static Scanner keyboardInput = new Scanner(System.in);
		      
    // ------------------ METHODS ------------------------  
    
    /* Main method */
    
    public static void main(String[] args) {
        final int COUNTER=0;
	
        // Input a natural number
        int natDecNumber = inputNatNum();
	
        // Do the conversion
	Dec2Bin newDec2Bin = new Dec2Bin();
        newDec2Bin.convertDec2Bin(natDecNumber,COUNTER);
	
	// End	
	System.out.println();  
        }
	
    /* Input a natural number */
    
    private static int inputNatNum() {
        int number;
        final int MAXIMUM = Integer.MAX_VALUE;
	final int MINIMUM = 0;
	
	// Invitation to input
        System.out.println("Input an integer between " + MINIMUM + 
        		" and " + MAXIMUM + " (inclusive)");

        // Do-while loop
        do {
            number = keyboardInput.nextInt();
	    if (number < MINIMUM || number > MAXIMUM) 
	    		System.out.println("ERROR 1: Incorrect input " + 
					number + ", try again!"); 
	    else break;		
            } while (true);

        // End
        return(number);
        }
    }

Table 2: Implementation for Dec2BinApp class


2.4. Testing

2.4.1. Black box testing

We should test the code using appropriate BVA analysis, and limit and arithmetic testing. We know the range of the natural number input defined in the Dec2BinApp class and thus the test cases presented in the table are suggested.

2.4.2. White box testing

TEST CASE EXPECTED RESULT
decimalNumber OUTPUT
-1 ERROR 1, Try agian!
0 00000000 00000000 00000000 00000000
1 00000000 00000000 00000000 00000001
1073741823 00111111 11111111 11111111 11111111
2147483646 01111111 11111111 11111111 11111110
2147483647 01111111 11111111 11111111 11111111
2147483648 ERROR, Exit

Path testing: We should test all paths identified in the flow chart given in Figure 11. This is already achieved by the above test cases.

Loop testing: The loop is a variable count loop therefore we should test the the loop with 1, 2 and some other number of passes through the loop. Again this will be achieved by the test cases given above.

2.4.2. Data validation testing

This should also be done.

2.4.3. Evidance of Testing

Some sample output is presented in Table 3.

$ java Dec2BinApp
Input an integer between 0 and 2147483647 (inclusive)
-1
ERROR 1: Incorrect input -1, try again!
0
00000000 00000000 00000000 00000000
[frans@frans Bin2Dec]$ java Dec2BinApp
Input an integer between 0 and 2147483647 (inclusive)
9999
00000000 00000000 0010011100001111
[frans@frans Bin2Dec]$

Table 3: Sample output from code presented in Table 2




3. DECIMAL TO HEXADECIMAL CONVERSION

The recursive approach described above can be adapted to other types of integer conversion. For example decimal to hexadecimal conversion. The implementation for a suggested class Dec2Hex is presented in Table 4 (class digarm in Figure 12).

Figure 12: Class diagarm for Dec2Hex conversion Class.

 

Notes on code presented in Table 4

The MAX_NUM_DIGITS constant is set to 3 becasuse the maximum number of digits to a 32 bit hexadecimal number is 4 (the count starts with digit 0).
Note the use of the characters symbols 'A' through to and including 'F' to indicate the extra 6 digits available in the hexadecimal system.
The Dec2Hex class presented here is designed to be used in conjunction with an application class very similar to the Dec2BinApp class introduced above (Table 2).
// DECIMAL TO HEXADECIMAL COMVERSION
// Frans Coenen
// Thursday 1 July 1999
// The University of Liverpool, UK   

class Dec2Hex {
    
    // ------------------ FIELDS ------------------------
     
    private static final int MAX_NUM_DIGITS = 3;
    
    // ------------------ METHODS ------------------------  
    
    /* ------ OUTPUT HEXADECIMAL NUMBER ------ */
    
    /* Output a hexadecimal number with leading zeroes. */
    
    public void convertDec2Hex(int number, int count) {
        final int HEX_BASE=16;
	       
        // Base case 

	if (number < HEX_BASE) {
		padWithZeros(count);
		outputHexDigit(number);
        	}
		
	// Recursive step
                   
        else {     
              convertDec2Hex(number/HEX_BASE,count+1);
              outputHexDigit(number%HEX_BASE);
              }   
        }
    
    /* ------ PAD WITH ZEROS ------ */

    // Private class method to output a sequence of `0' characters to 
    // pad the output with, where the hexadecimal number does not require 
    // all the available digits for its encoding. 

    private static void padWithZeros(int digitCount) {
        int loopParameter;
        int endValue = MAX_NUM_DIGITS-digitCount;

        // For loop, output a `0' on each iteration

        for(loopParameter=1;loopParameter< =endValue;loopParameter++) 
            System.out.print(0x0); 
        }
	
    /* ------ OUTPUT HEXADECIMAL DIGIT ------ */
    	
    /* Output a hexadecimal digit */
    
    private static void outputHexDigit(int digit) {
    	
	// Less than 10 not a problem.
	
	if (digit < 10) System.out.print(digit);
	
	// Else determine and iutput appropriate alphabetic literal
	
	else {
	    switch (digit) {
	        case 10:
		    System.out.print('A');
		    break;	
	        case 11:
		    System.out.print('B');
		    break;	
	        case 12:
		    System.out.print('C');
		    break;
	        case 13:
		    System.out.print('D');
		    break;
	        case 14:
		    System.out.print('E');
		    break;
	        default:
	            System.out.print('F');
	        }
	    }
        }
    }    

Table 4: Implementation for dec2hex class

The application class to accompany the code presented in Table 4 is almost identical to that presented in table 2.




ALTERNATIVE (RECURSIVE) IMPLEMENTATION OF FIBONACCI PROBLEM

In an earlier part of this "Introduction to Programming in Java" module we designed and implemented a program to output the Fibonacci sequence, using a for loop construct, up to a number of terms specified by the user (maximum of 45). An alternative approach to this problem is to use a recursive approach as shown in Table 5 and the applications class in Table 6. The class comprises a single method which calculates and returns the nth term in the Fibonacci sequence (unlike the previousn example method which output the entire sequence). The calculation is carried out using a double recursive technique to calculate pairs of terms that make up the next term. This approach nicely illustrates the use of this technique, however it is extremely inefficient.

// FIBONACCI CLASS (VERSION 2)
// Frans Coenen
// Wednesday 23 June 1999
// The University of Liverpool, UK

class FibonacciVer2 {

    // ------------------ METHODS ---------------------
    
    /* Calculate and output Fibonacci sequence */
    
    public int calcFibonacciSeq(int numberOfTerms) {
	
	switch (numberOfTerms) {		
	    case 1:
		return(0);
	    case 2:
		return(1);
	    default:
		return(calcFibonacciSeq(numberOfTerms-1) + 
				calcFibonacciSeq(numberOfTerms-2));
	    }
	}
    }

Table 5: Implementation for FibonacciVer2 class

// FIBONACCI APPLICATION CLASS (VERSION 2)
// FIBONACCI APPLICATION CLASS
// Frans Coenen
// Wednesday 23 June 1999
// Revised: Friday 26 August 2005
// The University of Liverpool, UK
   
import java.util.*;
   
class FibonacciVer2App { 
 
    // ------------------- FIELDS ------------------------ 
                      
    // Create Scanner class instance
    public static Scanner keyboardInput = new Scanner(System.in);
     
    // ------------------ METHODDS -----------------------
    
    /* Main method  */

    public static void main(String[] args) {
    	int numTerms;
	final int MAX_TERMS = 45;
	final int MIN_TERMS = 0;
	
	// Input number of terms	
	System.out.println("Input Number of terms (int " + MIN_TERMS + 
					".." + MAX_TERMS + "): ");
	do { 
    		numTerms = keyboardInput.nextInt();
		} while (numTerms < MIN_TERMS || numTerms > MAX_TERMS);
		
	// Create instance of class Fibonacci	
	FibonacciVer2 newFibonacci = new FibonacciVer2();
	
	// Calculate and output result	
	System.out.println("fib(" + numTerms + ") = " + 
			newFibonacci.calcFibonacciSeq(numTerms));		
        }
    }

Table 6: Implementation for FibonacciVer2App class




Created and maintained by Frans Coenen. Last updated 04 December 2006