Topic 2 : Recursion
Data Structures & Algorithms
Analysis
1
Chapter Contents
What Is Recursion?
Tracing a Recursive Method
Recursive Methods That Return a Value
Recursively Processing an Array
Recursively Processing a Linked Chain
A Simple Solution to a Difficult Problem
A Poor Solution to a Simple Problem
Calling Trees
Indirect Recursion
Tail Recursion
Learning Objectives
At the end of this lesson, the student
should be able to:
identify program with recursive method,
trace recursive method,
write recursive method, and
identify tail recursion and replace it with
iteration.
What Is Recursion?
It is a problem-solving process that can be used to
generate simple solutions (design of algorithm).
Technique related to repetition. It is an alternative way
of solving repetition problem.
Breaking a problem into identical but smaller
problems. The smaller problems are identical except
for their size.
Eventually you reach a smallest problem
Answer is obvious or trivial
Using that solution enables you to solve the previous
problems
Eventually the original problem is solved 4
Applications of Recursive
Algorithms
The fields of Artificial Intelligent – games, proving
mathematical theorems, recognizing patterns, etc.
Mathematical operations – computing factorial, greatest
common divisors, exponential functions, printing
permutations, etc.
Operations on data structures – String, array, list, tree,
graph, etc.
To design very efficient searching techniques - linear
and binary search.
Divide and conquer algorithms – sorting techniques,
etc.
Backtracking algorithms – puzzle, nonlinear data
structures traversal, etc.
What Is Recursion?
Fig. 1 : Counting down from 10.
What Is Recursion?
A method that calls itself is a recursive method
/** Task: Counts down from a given positive integer.
* @param integer an integer > 0 */
public static void countDown(int integer)
{ System.out.println(integer);
if (integer > 1)
countDown(integer - 1);
} // end countDown
The invocation is a
Recursive call, or
Recursive invocation
Recursive Methods
A recursive method is one that calls itself. Each
time it is called, the recursive method can operate
on different arguments.
Generally, a recursive solution is slightly less
efficient, in terms of computer time, than an
iterative one because of the overhead for the extra
method calls.
In many instances, however, recursion enables us
to specify a natural, simple solution to a problem
that otherwise would be difficult to solve.
When Designing Recursive
Solution
Recognize the base case and provide solution
to it.
Devise a strategy to split the problem into
smaller versions of itself. Each recursive case
must make progress towards the base case.
Combine the solutions to the smaller problem in
such a way that each larger problem is solve
correctly.
When Designing Recursive
Solution
Requirements of recursive method:
Must have one (or more) base cases
The general case (recursive case) must
eventually be reduced to the base case.
When Designing Recursive
Solution
Method definition must provide parameter (s)
Leads to different cases
Typically includes an if or a switch statement
One or more of these cases should provide a
non recursive solution
The base or stopping case
One or more cases includes recursive
invocation
Takes a step towards the base case
Two forms for recursive
algorithms
if the stopping case is reached
Solve it.
else
Split the problem into simpler cases using
recursion.
if the stopping case is not reached
Split the problem into simpler cases using recursion.
Tracing a Recursive Method
For each call to a method (be it recursive
or not), java records the state of the
method, including the values of its
parameters and local variables.
Each record, called an activation record,
is analogous to a piece of paper.
The records are placed into an ADT
called a stack.
Tracing a Recursive Method
public static void countDown(int integer)
{ System.out.println(integer);
if (integer > 1)
countDown(integer - 1);
} // end countDown
The effect of method call countDown(3)
Tracing a Recursive Method
Tracing the recursive call
countDown(3)
Tracing a Recursive Method
The stack of activation records during the execution of a
call to countDown(3)… continued →
Tracing a Recursive Method
Note: the recursive
method will use more
memory than an
iterative method due
to the stack of
activation records
The stack of activation records during the execution of a
call to countDown(3)
Recursive Methods That Return
a Value
Task: Compute the sum
1 + 2 + 3 + … + n for an integer n > 0
public static int sumOf(int n)
{
if (n = = 1)
return 1; // base case
else
return n + sumOf(n - 1);// recursive case
} // end sumOf
Recursive Methods That Return
a Value
The stack of activation records
during the execution of a call to sumOf(3)
Recursive Methods That Return
a Value (factorial function)
public static long fac(int n) A function definition:
{
if (n <= 1) 1 if n=1 or n=0
return 1; fac(n) = n * fac(n-1) if n>1
else
return n * fac(n-1)
}
fac(4) // 24
return 4* fac(3) // 4 * 6 = 24
return 3* fac(2) // 3 * 2 = 6
return 2 * fac(1) // 2 * 1= 2
return 1
Recursive Tree (Calling Tree)
Given a function definition of f(n) :
n if n<=1
f(n) = n + f(½n) if n is even number, and n>1
f(½ (n+1)) + f(½ (n-1)) if n is odd number, and n>1
If n=-5
F (-5)
-5
Recursive Tree (Calling Tree)
If n= 10
n if n<=1
f(n) = n + f(½n) if n is even number, and n>1
f(½ (n+1)) + f(½ (n-1)) if n is odd number, and n>1
F (10)
10+7=17
10 F (5)4+3=7
F (3) F (2)
F (1) 2+1=3
F (2) F (1)
3+1=4
2
2+1=3 F (1) 1 1
2
1 1
1
1
Recursively Processing an Array
Some of the more powerful searching and
sorting algorithms often are stated
recursively (usually is implemented using
an array)
When processing array recursively, divide
it into two pieces, for example;
Last element one piece, and the rest of the
array could be the other piece, or
First element one piece, and the rest of the
array could be the other piece, or
Divide the array into two halves
Recursively Processing an Array
public static void displayArray(int array[], int first, int
last)
{
System.out.print(array[first] + “ ”);//start from 1st element
if (first< last)
displayArray(array, first+1, last);
} // end display Array
public static void displayArray(int array[], int first, int
last)
{
if (first<= last)
{
displayArray(array, first, last-1);
System.out.print(array[last] + “ ”);//start from last
}
} // end display Array
Recursively Processing an Array
public static void displayArray(int array[], int first, int last)
{
if (first== last)
System.out.print(array[first] + " ");
else
{
int mid = (first + last)/2;
displayArray(array, first, mid);
displayArray(array, mid+1, last);
}
} // end display Array
Two arrays with middle elements within left halves
Recursively Processing a Chain of
Linked Nodes
To write a method that processes a chain of
linked nodes recursively
Use a reference to the chain's first node as the
method's parameter
public void display()
Then process { displayChain(head);
the first node System.out.println();
} // end display
Followed by the private void displayChain(Node current)
rest of the chain { if (current != null)
{ System.out.print(current.data + " ");
displayChain(current.next);
}
} // end displayChain
A Simple Solution to a Difficult
Problem
The initial configuration of the Towers of Hanoi
for three disks
A Simple Solution to a Difficult
Problem
Rules for the Towers of Hanoi game
1. Move one disk at a time. Each disk you
move must be a topmost disk.
2. No disk may rest on top of a disk smaller
than itself.
3. You can store disks on the second pole
temporarily, as long as you observe the
previous two rules.
A Simple Solution to a Difficult
Problem
The smaller problems in
a recursive solution for
four disks
A Simple Solution to a Difficult
Problem
Algorithm for solution with 1 disk as the base
case
Algorithm solveTowers(numberOfDisks, startPole, tempPole, endPole)
if (numberOfDisks == 1)
Move disk from startPole to endPole
else
{
solveTowers(numberOfDisks-1, startPole, endPole, tempPole)
Move disk from startPole to endPole
solveTowers(numberOfDisks-1, tempPole, startPole, endPole)
}
A Poor Solution to a Simple
Problem
Fibonacci numbers
First two numbers of sequence are 1 and 1
Successive numbers are the sum of the
previous two
1, 1, 2, 3, 5, 8, 13, …
This has a natural looking recursive
solution
Turns out to be a poor (inefficient) solution
A Poor Solution to a Simple
Problem
The recursive algorithm
Algorithm Fibonacci(n)
if (n <= 1)
return 1
else
return Fibonacci(n-1) + Fibonacci(n-2)
A Poor Solution to a Simple
Problem
Time efficiency grows
exponentially with n
int fib(int n){
int i, twoBack, oneBack, current;
if (n <= 1)
return 1;
else {
twoBack=0; oneBack=1;
for (i=2; i<=n;i++){
current=twoBack + oneBack;
twoBack=oneBack;
oneBack=current;
}
Iterative solution is O(n) return current;
}
}
The computation of the Fibonacci number F6
(a) recursively; (b) iteratively
Calling Trees
• Definition:
Fn = Fn-1 + Fn-2 , if n > 1
Fn = n, if n = 0 or 1
Indirect Recursion
Direct recursion is a
function calling itself.
When f() calls g() and
g() calls f(), we have
mutual recursion.
More generally, cycle
of function calls is
known as indirect
recursion.
Tail Recursion
Occurs when the last action performed by a
recursive method is a recursive call
public static void countDown(int integer)
{ System.out.println(integer);
if (integer > 1)
countDown(integer - 1);
} // end countDown
This performs a repetition that can be done more
efficiently with iteration
Conversion to iterative method is usually
straightforward
Tail Recursion
The significance of tail recursion is that when making a
tail-recursive call, the caller's return position need not
be saved on the call stack; when the recursive call
returns, it will branch directly on the previously saved
return position. Therefore, on compilers which support
tail-recursion optimization, tail recursion saves both
space and time.
//INPUT: Integers x, y such that x >= y and y > 0
int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
Conclusion
Advantage of implementing recursion:
Code is more simpler : easy to understand
and to write code.
Disadvantage:
Use more memory (activation records)
Conclusion
Q & A Session
References
Data Structures and Abstractions with Java . Authors:
Frank M. Carrano & Walter Savitch . Chapter 10
Data structures with Java. Authors : Hubbard J.R. &
Huray A. Chapter 10
40
