0% found this document useful (0 votes)
7 views29 pagesRecursion - Compressed
Chapter Five discusses recursion, defining it as a method that calls itself to solve problems like tree traversals and depth-first searches. It outlines key concepts such as base cases, recursive cases, and various types of recursion including direct, indirect, nested, tail, and linear recursion. The chapter also includes examples of recursive methods, their complexities, and how to analyze them using recurrence relations.
Uploaded by
michaelugo796Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
7 views29 pagesRecursion - Compressed
Chapter Five discusses recursion, defining it as a method that calls itself to solve problems like tree traversals and depth-first searches. It outlines key concepts such as base cases, recursive cases, and various types of recursion including direct, indirect, nested, tail, and linear recursion. The chapter also includes examples of recursive methods, their complexities, and how to analyze them using recurrence relations.
Uploaded by
michaelugo796Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Chapter Five
Recursion
5.1. Introduction
The process in which a method calls itself directly or indirectly is called recursion and the
corresponding method is called as recursive method. Recursion allows us to solve certain
problems such as tree traversals and depth-first search of a graph quite easily and expressively,
Each time a recursive method calls itself, the method is supplied with a smaller version of the
original problem. This process continues until the problem cannot be reduced any further
(simplest possible problem).
To solve a problem recursively, one has to identify:
© the base case,
the recursive case and
‘+ away to approach the base case through the recursive case.
The base case is the solution when a method is supplied with the simplest possible problem;
while the recursive case is the solution that breaks down a complex problem into simpler ones,
‘A recursion tree may be drawn to visualize how a recursive method arrives at the solution to a
given problem. The root of the tree represents the initial call to the recursive method. Every
internal node represents a subsequent recursive call while the leaf nodes represent cither the
base case or other non-recursive operation.
‘There are different types of recursive methods. The difference is in the implementation of the
recursive case:
* Direct recursion: In direct recursion, the method calls itself directly while in indirect
recursion, the method calls itself indirectly via another method.
© Nested recursion: In nested recursion, the method has the recursive case defined as
‘one of its parameters in the recursive function. While a non-nested recursive method
always has the recursive case in the body of the method.
© Tail recursion: A tail recursive methods do not have pending operations after a
recursive call while a non-tail recursive method has pending operations after a
recursive call.
* Linear recursion: A linear recursive method only makes one recursive call in the
recursive case while a tree recursive method makes more than one recursive calls in
the recursive case.
Excessively recursion: In excessive recusion, methods repeat computations for some
parameter values.
Note that a recursive method may belong to more than one of these categories at the same time.
134 We can measure and analyse the complexity (running time) of recursive methods. This can be
achieved by deriving equations (in terms of its input) that represent the operations of the
method, These equations are called recurrence relations expressed as a function of » (input
size) convensionally denoted by 7(n). Two recurrence relations are typically derived: one that
represents the base case and the other represents the recursive case, The complexity is then
determined by finding an asymptotic bound on the recurrence relation.
To solve a recurrence relation, we necd to derive a closed form expression from the recurrence
relation, Using iteration method, the following steps are followed when solving a recurrence
relation:
‘© Iteratively expand the recurrence equation by plugging the recurrence back into itself
until a pattern is observed.
© Evaluate 7).
‘Match the resulting equation with any standard summation formulae (see a list of
some summation formulae below).
Evaluate the summation,
Determine the Big-O complexity
Here is a list of some standard summation formulae:
1. Sesen
_n(n+))
2,
2
3, Sgt = MED n +)
ra 6
ay we -[seeny
= 2
5.
6.
1.
12. Saceey = Mert hn+2)
3
135 5.2. Solved Problems
Example 5.1 Implementing and Analysing the Factorial Method
Write a recursive method for the famous factorial function. Determine the complexity of the
method.
Solution to Example 5.1
The method is shown in Listing 5.1. Clearly, the base case is when the input n is equal
to 0, lines 2-3 and the recursive case is when n>0, line 5.
1. public static void factorial (int n){
2 if (n == 0)
3. return 1;
4. el
5. return n*factorial(n-1);
6.)
Listing 5.1: Recursive method factorial
This is a linear recursive function, as discussed earlier, because there is only a single call to the
recursive method, as shown in line 5,
Figure 5.1: Recursion Tree for the Call factorial(3)
‘The recusion tree for the call factorial(3) is shown in Figure 5.1. We called the methos is @
small parameter value, 3, for illustration only. The tree will have the same shape for larger
parameter values. The number below each call in the figure is the value returned by the call
just above the value, ‘That is, factorial(0) is 1, factorial(1) is 1, factorial(2) is 2 and
factorial(3) is 6.
136 Time Complexity of Listing 5.1
Let T(n) be the amount of work done by the method factorial on an integer n. The base case
is when n = 0, when the method makes one comparison at line 2 and then returns at line 3.
‘That is, when n = 0, factorial performs a constant number of operations, say a. The equation
for the base case, therefore, can be written as:
7) =a
For the recursive case, when n > 0, the method also performs a constant number of operations
(the comparison at line 2 and the multiplication at line 5), say b, before calling the method on
a smaller parameter, (n — 1), line 5. The equation for the recursive case, therefore, can be
written as:
T(n)=T(n-1)+6).
For the factorial method, therefore, we have the recurrence relation:
rm) ={ Se, TO
T(n-1)+b, n>0
To solve the recurrence relation, we will repeatédly plug in the relation for 7(n) into itself until
a pattern is observed:
TO)
T(n)=TOr=1) +b
Expand 7(n~ 1) and substitute into T(n):
T(n)=T((n-1)-1)+b+b
=7(n-2)+26
=T(n-3)+%
‘A pattern is obvious so we can generalise:
T(n)=T(n-K) +k
Letk=n
T(n)=7(n-n)+(n)b
=T(O)+bn
Recall that 7(0) = a. So we have:
T(n)=a+bn
This is a simple linear equation where the dominant variable is n. Therefore, the factorial is
0m).
Example 5.2 Implementing and Analysing a Method for Printing 1 toN
Write a recursive method to print all numbers between I toN. Determine the complexity of
the method,
137 Solution to Example 5.2
The method implementation is shown in
example,
ing 5.2. Itis very similar to the preceding
+ public static void printIToN (int n){
if (n == 0)
return;
Print1ToN(n-1) ;
System. out.print1n(n) ;
Listing 5.2: Recursive method print TON
‘Time Complexity of Listing 5.2
The structure of this method is very similar to the one of factorial in the preceding example.
Let T(n) be the amount of work done by the method printiToN on an integer n. The base
case is when n = 0, when the method makes one comparison at line 2 and then returns at line
3. That is, when n = 0, printIToN performs a constant number of operations, say a. The
‘equation for the base case, therefore, can be written as:
T(0) =
For the recursive case, when n > 0, the method also performs a constant number of operations
(the comparison at line 2 and the printing at line 5. Note that this printing will be delayed until
the call will parameter (n— 1) completes), say b, before calling the method on a smaller
parameter, (n ~ 1), line 4. The equation for the recursive case, therefore, can be written as:
T(n)=T(n-1)+b).
For the print TON method, therefore, we have the recurrence relation:
a n=0
Tin) = tron +b, n>0
‘This recurrence relation is the same as the one in the preceding example. Therefore, the
complexity of the print! TON method is O(n).
Example 5.3 Converting Method printIToN to Tail Recursive
Convert the non-tail recursive method in
ng 5.2 t0 a til recursive version,
Solution to Example 8.3
Remember that tal recursive methods are methods that do not have pending operations after a
recursive call. The method printIToN, Listing 5.2, is clearly not a tail recursive method
because of the printin statement after the recursive call.
Interchanging the statements at line 4and line 5 will not yield entirely the desired result as the
‘outcomie of the recursive method will be affected (try it out). A way of solving this problem is
to introduce an auxiliary parameter which will be printed when the base case is reached, as
shown in Listing 5.3.
138 1. public static void printiToN(int n, String accumulator) {
2, d£tn == 0){
3 System. out .print1n (accumulator) ;
a return;
5 )
6. printlToN(n-1, n +"\n" + accumulator);
ny
Listing 5.3: A Tail Recursive Version of Method print\ToN
We can make the interface to the method cleaner and simpler by also introducing an
auxiliary method, as shown in Listing 5.4.
1, public static void printiToN(int n) (
2. printiToNAux(n, "*);
3.2)
4. public static void printiToNAux(int n, String accumulator) {
5. if(n