Databases Development

Mulungushi University
School of Science, Engineering and
Technology
ICT202 Data Structures and Algorithms
Lecture 3

© 1992-2007 Pearson Education, Inc. All rights reserved.

 2

1. Introduction
2. Recursion Concepts
3. Example Using Recursion: Factorials
4. Example Using Recursion: Fibonacci Series
5. Recursion and the Method Call Stack
6. Recursion vs. Iteration
7. Towers of Hanoi
8. Dynamic Programming
9. Recursive Backtracking

© 1992-2007 Pearson Education, Inc. All rights reserved.

Recursive Thinking
• Recursion is a programming technique in
which a method can call itself in order to
fulfill its purpose
• A recursive definition is one which uses the
word or concept being defined in the
definition itself
• In some situations, a recursive definition can
be an appropriate way to express a concept
• Before applying recursion to programming, it
is best to practice thinking recursively
© 1992-2007 Pearson Education, Inc. All rights reserved.
Recursion

• Recursion: when a method calls itself

• Classic example- - the factorial function:
• n! = 1· 2· 3· ··· · (n-1)· n
• Recursive definition:
• f(n) = 1 if n=0
• f(n) = n * (n-1)! If n> 0

© 1992-2007 Pearson Education, Inc. All rights reserved.

 Recursive Programming
• A method in Java can invoke itself; if set up that way,
it is called a recursive method
• The code of a recursive method must be structured to
handle both the base case and the recursive case
• Each call sets up a new execution environment, with
new parameters and new local variables
• As always, when the method completes, control returns
to the method that invoked it (which may be another
instance of itself)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 Recursive Programming
• Consider the problem of computing the sum of all the
numbers between 1 and N, inclusive
• If N is 5, the sum is
1+2+3+4+5
• This problem can be expressed recursively as:

The sum of 1 to N is N plus the sum of 1 to N-1

© 1992-2007 Pearson Education, Inc. All rights reserved.

The sum of 1 to N, defined recursively

N N −1

i = N + i
i =1 i =1
N −2
= N + N −1 +  i
i =1
N −3
= N + N − 1 + N − 2 + i
i =1

= N + N −1 + N − 2 +  + 2 +1

© 1992-2007 Pearson Education, Inc. All rights reserved.

 Recursive Programming
public int sum (int num)
{
int result;
if (num == 1)
Base case
result = 1;
else
Recursive result = num + sum(num-1);
case return result;
}

© 1992-2007 Pearson Education, Inc. All rights reserved.

Recursive calls to the sum method
result = 4 + sum(3)
main

sum(4) result = 3 + sum(2)

sum

result = 2 + sum(1)
sum(3)
sum

sum(2) result = 1
sum

sum(1)
sum

© 1992-2007 Pearson Education, Inc. All rights reserved.

Recursive method

• Base case(s).
– Values of the input variables for which we perform no
recursive calls are called base cases (there should be at
least one base case).
– Every possible chain of recursive calls must eventually
reach a base case.
• Recursive calls.
– Calls to the current method.
– Each recursive call should be defined so that it makes
progress towards a base case.

© 1992-2007 Pearson Education, Inc. All rights reserved.

Visualizing Recursion
• fact(4) => 4 x fact(4-1)
• => 4 x fact(3)
• => 4 x (3 x fact(3-1))
• => 4 x (3 x fact(2))
• => 4 x (3 x (2 x fact(2-1)))
• => 4 x (3 x (2 x fact(1)))
• => 4 x (3 x (2 x (1 x fact(1-1))))
• => 4 x (3 x (2 x (1 x fact(0))))
• => 4 x (3 x (2 x (1 x 1)))
• => 4 x (3 x (2 x 1))
• => 4 x (3 x 2) => 4 x 6 =>24

© 1992-2007 Pearson Education, Inc. All rights reserved.

 12

Recursion problem solving elements

• Base case
– Recursive method capable of solving only simplest case—the base case
– If method is called with base case, method returns result
• If method is called with more complex problem, problem
divided into two pieces—a piece the method knows how to
do and a piece the method does not know how to do
(called recursive call or recursion step)
• Recursive call/recursion step
– Must resemble original problem but be slightly simpler or smaller
version
– Method calls fresh copy of itself to work on smaller problem
– Normally includes return statement

© 1992-2007 Pearson Education, Inc. All rights reserved.

 13

Example Using Recursion: Factorials

• Factorial of n, or n! is the product

n · (n – 1) · (n – 2) · … · 1
With 1! equal to 1 and 0! Defined to be 1.
• Can be solved recursively or iteratively (nonrecursively)
• Recursive solution uses following relationship:
n! = n · (n – 1)!
• Infinite recursion – recursive calls are continuously made
until memory has been exhausted
– Caused by either omitting base case or writing recursion step
that does not converge on base case

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.3: FactorialCalculator.java 14
2 // Recursive factorial method.
3
4 public class FactorialCalculator
5 {
6 // recursive method factorial
7 public long factorial( long number )
8 { Base case returns 1
9 if ( number <= 1 ) // test for base case
10 return 1; // base cases: 0! = 1 and 1! = 1
11 else // recursion step
Recursion step breaks problem into two parts: one the
12 return number * factorial( number - 1 ); method knows how to do, one the method does not
13 } // end method factorial
14
15 // output factorials for valuesPortion
0-10 methodRecursive
knows howcall:
to Portion
do method does not know how to
16 public void displayFactorials() do; smaller version of original problem
17 {
18 // calculate the factorials of 0 through 10
19 for ( int counter = 0; counter <= 10; counter++ )
20 System.out.printf( "%d! = %d\n", counter, factorial( counter ) );
21 } // end method displayFactorials
22 } // end class FactorialCalculator
Original call to recursive method

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.4: FactorialTest.java 15
2 // Testing the recursive factorial method.
3
4 public class FactorialTest
5 {
6 // calculate factorials of 0-10
7 public static void main( String args[] )
8 {
9
Calculate and display factorials
FactorialCalculator factorialCalculator = new FactorialCalculator();
10 factorialCalculator.displayFactorials();
11 } // end main
12 } // end class FactorialTest

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

© 1992-2007 Pearson Education, Inc. All rights reserved.

 16

Fig. 15.2 | Recursive evaluation of 5!.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 17

Example Using Recursion: Fibonacci

Series
• Fibonacci series begins with 0 and 1 and has property that
each subsequent Fibonacci number is the sum of previous
two Fibonacci numbers.
• Series occurs in nature, ratio of successive Fibonacci
numbers converges on golden ratio or golden mean
• Fibonacci series defined recursively as:
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
• Recursive solution for calculating Fibonacci values results
in explosion of recursive method calls

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.5: FibonacciCalculator.java 18
2 // Recursive fibonacci method.
3
4 public class FibonacciCalculator
5 {
6 // recursive declaration of method fibonacci
Two base cases
7 public long fibonacci( long number )
8 {
9 if ( ( number == 0 ) || ( number == 1 ) ) // base cases Two recursive calls
10 return number;
11 else // recursion step
12 return fibonacci( number - 1 ) + fibonacci( number - 2 );
13 } // end method fibonacci
14
15 public void displayFibonacci()
16 {
17 for ( int counter = 0; counter <= 10; counter++ )
18 System.out.printf( "Fibonacci of %d is: %d\n", counter,
19 fibonacci( counter ) );
20 } // end method displayFibonacci
21 } // end class FibonacciCalculator
Original call to recursive method

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.6: FibonacciTest.java 19
2 // Testing the recursive fibonacci method.
3
4 public class FibonacciTest
5 {
6 public static void main( String args[] )
7 {
8 Calculate and display
FibonacciCalculator fibonacciCalculator = new FibonacciCalculator(); Fibonacci values
9 fibonacciCalculator.displayFibonacci();
10 } // end main
11 } // end class FibonacciTest

Fibonacci of 0 is: 0
Fibonacci of 1 is: 1
Fibonacci of 2 is: 1
Fibonacci of 3 is: 2
Fibonacci of 4 is: 3
Fibonacci of 5 is: 5
Fibonacci of 6 is: 8
Fibonacci of 7 is: 13
Fibonacci of 8 is: 21
Fibonacci of 9 is: 34
Fibonacci of 10 is: 55

© 1992-2007 Pearson Education, Inc. All rights reserved.

 20

Fig. 15.7 | Set of recursive calls for fibonacci( 3 ).

© 1992-2007 Pearson Education, Inc. All rights reserved.

 21

Recursion and the Method Call Stack

• Method call stack used to keep track of method

calls and local variables within a method call
• Just as with nonrecursive programming,
recursive method calls are placed at the top of the
method call stack
• As recursive method calls return, their activation
records are popped off the stack and the previous
recursive calls continue executing
• Current method executing is always method
whose activation record is at top of stack

© 1992-2007 Pearson Education, Inc. All rights reserved.

 22

Fig. 15.8 | Method calls made within the call fibonacci( 3 ).

© 1992-2007 Pearson Education, Inc. All rights reserved.

 23

Fig. 15.9 | Method calls on the program execution stack.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 24

Towers of Hanoi
• Classic problem – Priests in Far East are attempting to
move a stack of disks from one peg to another. One disk
must be moved at a time, at no time may a larger disk be
placed above a smaller disk

© 1992-2007 Pearson Education, Inc. All rights reserved.

 The Towers of Hanoi
• The Towers of Hanoi is a puzzle made up of three vertical
pegs and several disks that slide onto the pegs
• The disks are of varying size, initially placed on one peg
with the largest disk on the bottom and increasingly
smaller disks on top
• The goal is to move all of the disks from one peg to
another following these rules
– Only one disk can be moved at a time
– A disk cannot be placed on top of a smaller disk
– All disks must be on some peg

© 1992-2007 Pearson Education, Inc. All rights reserved.

 26

Towers of Hanoi
• Recursive solution:
– Move n – 1 disks from peg 1 to peg 2, using peg
3 as temporary holding area
– Move the last disk (the largest) from peg 1 to peg
3
– Move the n – 1 disks from peg 2 to peg 3, using
peg 1 as a temporary holding area
• Base case: When only one disk needs to be moved –
no temporary holding area needed, disk is simply
moved

© 1992-2007 Pearson Education, Inc. All rights reserved.

 27

1. Move the top disk from peg 1 to peg 3.

2. Move the second disk from peg 1 to peg 2.
3. Move the top disk from peg 3 to peg 2.
4. Move the remaining disk from peg 1 to peg 3.
5. Move the top disk from peg 2 to peg 1.
6. Move the second disk from peg 2 to peg 3.
7. Move the top disk from peg 1 to peg 3.

© 1992-2007 Pearson Education, Inc. All rights reserved.

A solution to the 3-disk ToH puzzle

© 1992-2007 Pearson Education, Inc. All rights reserved.

Towers of Hanoi

• To move a stack of N disks from the original peg

to the destination peg
– Move the topmost N-1 disks from the original peg to the
extra peg
– Move the largest disk from the original peg to the
destination peg
– Move the N-1 disks from the extra peg to the destination
peg
• The base case occurs when a “stack” contains
only one disk

© 1992-2007 Pearson Education, Inc. All rights reserved.

Towers of Hanoi
• Note that the number of moves increases
exponentially as the number of disks increases
• The recursive solution is simple and elegant to
express (and program)
• An iterative solution to this problem is much
more complex

© 1992-2007 Pearson Education, Inc. All rights reserved.

 SolveTowers.java
//********************************************************************
// SolveTowers.java Java Foundations
//
// Demonstrates recursion by solving the classic Towers of Hanoi
// puzzle.
//********************************************************************

public class SolveTowers

{
//------------------------------------------------------------------
// Creates a TowersOfHanoi puzzle and solves it.
//------------------------------------------------------------------
public static void main (String[] args)
{
TowersOfHanoi towers = new TowersOfHanoi (4);
towers.solve();
}
}

© 1992-2007 Pearson Education, Inc. All rights reserved.

 TowersOfHanoi.java
//********************************************************************
// TowersOfHanoi.java Java Foundations
//
// Represents the classic Towers of Hanoi puzzle.
//********************************************************************

public class TowersOfHanoi

{
private int totalDisks;

//------------------------------------------------------------------
// Sets up the puzzle with the specified number of disks.
//------------------------------------------------------------------
public TowersOfHanoi (int disks)
{
totalDisks = disks;
}
(more…)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 TowersOfHanoi.java
//------------------------------------------------------------------
// Moves the specified number of disks from one tower to another
// by moving a subtower of n-1 disks out of the way, moving one
// disk, then moving the subtower back. Base case of 1 disk.
//------------------------------------------------------------------
private void moveTower (int numDisks, int start, int end, int temp)
{
if (numDisks == 1)
moveOneDisk (start, end);
else
{
moveTower (numDisks-1, start, temp, end);
moveOneDisk (start, end);
moveTower (numDisks-1, temp, end, start);
}
}
(more…)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 TowersOfHanoi.java
//------------------------------------------------------------------
// Performs the initial call to moveTower to solve the puzzle.
// Moves the disks from tower 1 to tower 3 using tower 2.
//------------------------------------------------------------------
public void solve ()
{
moveTower (totalDisks, 1, 3, 2);
}

//------------------------------------------------------------------
// Prints instructions to move one disk from the specified start
// tower to the specified end tower.
//------------------------------------------------------------------
private void moveOneDisk (int start, int end)
{
System.out.println ("Move one disk from " + start + " to " +
end);
}
}

© 1992-2007 Pearson Education, Inc. All rights reserved.

Towers of Hanoi

© 1992-2007 Pearson Education, Inc. All rights reserved.

Recursion vs. Iteration

• Just because we can use recursion to solve a

problem, doesn't mean we should
• For instance, we usually would not use recursion
to solve the sum of 1 to N
• The iterative version is easier to understand (in
fact there is a formula that is superior to both
recursion and iteration in this case)
• You must be able to determine when recursion is
the correct technique to use

© 1992-2007 Pearson Education, Inc. All rights reserved.

Recursion vs. Iteration

• Every recursive solution has a corresponding

iterative solution
• For example, the sum of the numbers between 1
and N can be calculated with a loop
• Recursion has the overhead of multiple method
invocations
• However, for some problems recursive solutions
are often more simple and elegant than iterative
solutions

© 1992-2007 Pearson Education, Inc. All rights reserved.

 38

Recursion vs. Iteration

• Any problem that can be solved recursively can be solved
iteratively
• Both iteration and recursion use a control statement
– Iteration uses a repetition statement
– Recursion uses a selection statement
• Iteration and recursion both involve a termination test
– Iteration terminates when the loop-continuation condition fails
– Recursion terminates when a base case is reached
• Recursion can be expensive in terms of processor time and
memory space, but usually provides a more intuitive
solution

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.10: FactorialCalculator.java 39
2 // Iterative factorial method.
3
4 public class FactorialCalculator
5 {
6 // recursive declaration of method factorial
7 public long factorial( long number )
8 {
9 long result = 1; Iterative solution uses counter-controlled repetition
10
11 // iterative declaration of method factorial
12 for ( long i = number; i >= 1; i-- )
13 result *= i;
14
15 return result;
16 } // end method factorial
17
18 // output factorials for values 0-10
19 public void displayFactorials()
20 {
21 // calculate the factorials of 0 through 10
22 for ( int counter = 0; counter <= 10; counter++ )
23 System.out.printf( "%d! = %d\n", counter, factorial( counter ) );
24 } // end method displayFactorials
25 } // end class FactorialCalculator

© 1992-2007 Pearson Education, Inc. All rights reserved.

1 // Fig. 15.11: FactorialTest.java 40

2 // Testing the iterative factorial method.

3
4 public class FactorialTest
5 {
6 // calculate factorials of 0-10
7 public static void main( String args[] )
8 {
9 FactorialCalculator factorialCalculator = new FactorialCalculator();
10 factorialCalculator.displayFactorials();
11 } // end main
12 } // end class FactorialTest

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

© 1992-2007 Pearson Education, Inc. All rights reserved.

 41
Another Iterative Implementation of the Factorial Function
1 public static int f(int n) {
2 int f = 1;
3 for (int i = 2; i <= n; i++) {
4 f *= i;
5}
6 return f;
7}
Here is a simple test driver for the factorial method:
1 public static void main(String[] args) {
2 for (int n=0; n<10; n++) {
3 System.out.println("f("+n+") = "+f(n));
4}
5}

© 1992-2007 Pearson Education, Inc. All rights reserved.

Direct vs. Indirect Recursion
• A method invoking itself is considered to be direct
recursion
• A method could invoke another method, which
invokes another, etc., until eventually the original
method is invoked again
• For example, method m1 could invoke m2, which
invokes m3, which invokes m1 again
• This is called indirect recursion
• It is often more difficult to trace and debug

© 1992-2007 Pearson Education, Inc. All rights reserved.

Direct vs. Indirect Recursion

m1 m2 m3

m1 m2 m3

m1 m2 m3

© 1992-2007 Pearson Education, Inc. All rights reserved.

 44

Dynamic Programming

• In most cases, recursion is very inefficient because

of its frequent function calls.
• So an iterative implementation may be better if it
is not too complex.
• Another alternative is to implement the
recurrence relation by storing previously
computed values in an array instead of
recomputing them with recursive function calls.
• This method is called dynamic programming.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 45

© 1992-2007 Pearson Education, Inc. All rights reserved.

 46

Recursive Backtracking

• Recursive Backtracking – process of using

recursion to return to earlier decision point
• If one set of recursive calls does not result in
solution, program backs up to previous decision
point and makes different decision, often
resulting in another set of recursive calls
• Examples (you can read)
– Maze problem
– Eight-Queens problem

© 1992-2007 Pearson Education, Inc. All rights reserved.

 47

Exercises
• Write a recursive definition of xy (x raised to the power y),
where x and y are integers and y > 0.
• Write a recursive definition of i * j (integer multiplication),
where i > 0. Define the multiplication process in terms of integer
addition. For example, 4 * 7 is equal to 7 added to itself 4 times.
• Write a recursive definition of the Fibonacci numbers. The
Fibonacci numbers are a sequence of integers, each of which is
the sum of the previous two numbers. The first two numbers in
the sequence are 0 and 1. Explain why you would not normally
use recursion to solve this problem.

© 1992-2007 Pearson Education, Inc. All rights reserved.

 48

Exercises
• Modify the method that calculates the sum of the integers
between 1 and N shown in this chapter. Have the new version
match the following recursive definition: The sum of 1 to N is
the sum of 1 to (N/2) plus the sum of (N/2 + 1) to N. Trace your
solution using an N of 7.
• Write a recursive method that returns the value of N! (N
factorial) using the definition given in this chapter. Explain why
you would not normally use recursion to solve this problem.
• Write a recursive method to reverse a string. Explain why you
would not normally use recursion to solve this problem.

© 1992-2007 Pearson Education, Inc. All rights reserved.

Maze Traversal
• Recursion will be used to keep
track of the path through the maze
using the run-time stack
• The base cases are
– a prohibited (blocked) move, or
– arrival at the final destination

© 1992-2007 Pearson Education, Inc. All rights reserved.

Solving a Maze
Start

End

© 1992-2007 Pearson Education, Inc. All rights reserved.

 MazeSearch.java
//********************************************************************
// MazeSearch.java Java Foundations
//
// Demonstrates recursion by solving a maze traversal.
//********************************************************************

public class MazeSearch

{
//------------------------------------------------------------------
// Creates a new maze, prints its original form, attempts to
// solve it, and prints out its final form.
//------------------------------------------------------------------
public static void main (String[] args)
{
Maze labyrinth = new Maze();

System.out.println (labyrinth);

if (labyrinth.traverse (0, 0))

System.out.println ("The maze was successfully traversed!");
else
System.out.println ("There is no possible path.");

System.out.println (labyrinth);
}
}
© 1992-2007 Pearson Education, Inc. All rights reserved.
 Maze.java
//********************************************************************
// Maze.java Java Foundations
//
// Represents a maze of characters. The goal is to get from the
// top left corner to the bottom right, following a path of 1's.
//********************************************************************

public class Maze

{
private final int TRIED = 3;
private final int PATH = 7;

private int[][] grid = { {1,1,1,0,1,1,0,0,0,1,1,1,1},

{1,0,1,1,1,0,1,1,1,1,0,0,1},
{0,0,0,0,1,0,1,0,1,0,1,0,0},
{1,1,1,0,1,1,1,0,1,0,1,1,1},
{1,0,1,0,0,0,0,1,1,1,0,0,1},
{1,0,1,1,1,1,1,1,0,1,1,1,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1,1,1,1} };

(more…)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 Maze.java
//------------------------------------------------------------------
// Attempts to recursively traverse the maze. Inserts special
// characters indicating locations that have been tried and that
// eventually become part of the solution.
//------------------------------------------------------------------
public boolean traverse (int row, int column)
{
boolean done = false;

if (valid (row, column))

{
grid[row][column] = TRIED; // this cell has been tried

if (row == grid.length-1 && column == grid[0].length-1)

done = true; // the maze is solved
else
{
done = traverse (row+1, column); // down
if (!done)
done = traverse (row, column+1); // right
if (!done)
done = traverse (row-1, column); // up
if (!done)
done = traverse (row, column-1); // left
}
(more…)
© 1992-2007 Pearson Education, Inc. All rights reserved.
 Maze.java
if (done) // this location is part of the final path
grid[row][column] = PATH;
}

return done;
}

//------------------------------------------------------------------
// Determines if a specific location is valid.
//------------------------------------------------------------------
private boolean valid (int row, int column)
{
boolean result = false;

// check if cell is in the bounds of the matrix

if (row >= 0 && row < grid.length && column >= 0 &&
column < grid[row].length)

// check if cell is not blocked and not previously tried

if (grid[row][column] == 1)
result = true;

return result;
}
(more…)

© 1992-2007 Pearson Education, Inc. All rights reserved.

 Maze.java
//------------------------------------------------------------------
// Returns a string representation of the maze.
//------------------------------------------------------------------
public String toString ()
{
String result = "\n";

for (int row = 0; row < grid.length; row++)

{
for (int column=0; column < grid[row].length; column++)
result += grid[row][column] + "";
result += "\n";
}

return result;
}
}

© 1992-2007 Pearson Education, Inc. All rights reserved.

Class Diagram for the maze program

© 1992-2007 Pearson Education, Inc. All rights reserved.