DSA with Java/Unit- 4

Unit 4: Recursion
Recursive Definitions
One of the basic rules for defining new objects or concepts is that the definition should contain
only such terms that have already been defined or that are obvious. Therefore, an object that is
defined in terms of itself is a serious violation of this rule—a vicious circle. On the other hand,
there are many programming concepts that define themselves. As it turns out, formal restrictions
imposed on definitions such as existence and uniqueness are satisfied and no violation of the rules
takes place. Such definitions are called recursive definitions, and are used primarily to define
infinite sets. When defining such a set, giving a complete list of elements is impossible, and for
large finite sets, it is inefficient. Thus, a more efficient way has to be devised to determine if an
object belongs to a set.
 Recursive Definitions: Defining something in terms of itself. (Example: Recursive
function/method)
 A recursive definition consists of two parts.
o In the first part, called the anchor or the ground case, the basic elements that are
the building blocks of all other elements of the set are listed.
o In the second part, rules are given that allow for the construction of new objects out
of basic elements or objects that have already been constructed. These rules are
applied again and again to generate new objects.
 Recursive definitions serve two purposes: generating new elements and testing whether an
element belongs to a set
 Recursive definitions are frequently used to define functions and sequences of numbers.
For instance, the factorial function, can be defined in the following manner:

Using this definition, we can generate the sequence of numbers 1, 1, 2, 6, 24, 120, 720,
5040, 40320, 362880, 3628800, . . . which includes the factorials of the numbers 0, 1, 2, .
. . , 10, . . .

1
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

 Recursive definitions of sequences have one undesirable feature: To determine the value
of an element sn of a sequence, we first have to compute the values of some or all of the
previous elements, s1, . . ., sn–1. For example, calculating the value of 3! requires us to first
compute the values of 0!, 1!, and 2!.
 Some uses of recursive definition:
 One area where recursive definitions are used extensively is in the specification of
the grammars of programming languages.
 Recursive definitions are also used in programming.
For example, we can implement the recursive definition of factorial in Java by using
following recursive method:
int factorial (int n) {
if (n == 0)
return 1;
else
return n * factorial (n – 1);
}
Note: Recursive definitions on most computers are eventually implemented using a run-time stack,
although the whole work of implementing recursion is done by the operating system, and the
source code includes no indication of how it is performed. E. W. Dijkstra introduced the idea of
using a stack to implement recursion.

Method Calls and Recursion Implementation

What happens when a method is called?
 If the method has formal parameters, they have to be initialized to the values passed as
actual parameters.
 In addition, the system has to know where to resume execution of the program after the
method has finished.
 The method can be called by other methods or by the main program (the method main())
 The information indicating where it has been called from has to be remembered by the
system. This could be done by storing the return address in main memory in a place set

2
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

aside for return addresses, but we do not know in advance how much space might be
needed, and allocating too much space for that purpose alone is not efficient.
 For a method call, more information has to be stored than just a return address. Therefore,
dynamic allocation using the run-time stack is a much better solution. It needs to be stressed
that the run-time stack is maintained by a particular operating system.
(Note: Java stack used by JVM and run-time stack are two different entities They are similar in
that their role in processing method calls is basically the same; therefore, they store similar
information that enables this processing, although they store this information differently)
What information should be preserved when a method is called?
 First, automatic (local) variables must be stored.
 The state of each method, including main(), is characterized by the contents of all automatic
variables, by the values of the method’s parameters, and by the return address indicating
where to restart its caller.
 The data area containing all this information is called an activation record or a stack frame
and is allocated on the run-time stack.
o An activation record exists for as long as a method owning it is executing
o Activation records usually have a short lifespan because they are dynamically
allocated at method entry and deallocated upon exiting.
o Only the activation record of main() outlives every other activation record
 An activation record usually contains the following information:
 Values for all parameters to the method, location of the first cell if an array is
passed or a variable is passed by reference, and copies of all other data items.
 Local (automatic) variables that can be stored elsewhere, in which case, the
activation record contains only their descriptors and pointers to the locations
where they are stored.
 The return address to resume control by the caller, the address of the caller’s
instruction immediately following the call.
 A dynamic link, which is a pointer to the caller’s activation record.
 The returned value for a method not declared as void. Because the size of the
activation record may vary from one call to another, the returned value is placed
right above the activation record of the caller.

3
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

 If a method is called either by main() or by another method, then its activation record is
created on the run-time stack. The run-time stack always reflects the current state of the
method.
 For example, suppose that main() calls method f1(), f1() calls f2(), and f2() in turn calls
f3(). If f3() is being executed, then the state of the run-time stack is as shown in following
figure .

Figure 1: Contents of the run-time stack when main() calls method f1(), f1() calls f2(),and f2() calls f3().

 By the nature of the stack, if the activation record for f3() is popped by moving the stack
pointer right below the return value of f3(), then f2() resumes execution and now has free
access to the private pool of information necessary for reactivation of its execution. On the

4
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

other hand, if f3() happens to call another method f4(), then the run-time stack increases its
height because the activation record for f4() is created on the stack and the activity of f3()
is suspended.
 Creating an activation record whenever a method is called allows the system to handle
recursion properly. Recursion is calling a method that happens to have the same name as
the caller. Therefore, a recursive call is not literally a method calling itself, but rather an
instantiation of a method calling another instantiation of the same original. These
invocations are represented internally by different activation records and are thus
differentiated by the system.

Anatomy of a Recursive Call

 The function that defines raising any number x to a nonnegative integer power n is a good
example of a recursive function. The most natural definition of this function is given by:

 A Java method for computing xn can be written directly from the definition of a power:

double power (double x, int n) {

if (n == 0)
return 1.0;
else
return x * power(x,n-1);
}
 Using this definition, the value of x4 can be computed in the following way:

 The repetitive application of the inductive step eventually leads to the anchor, which is the
last step in the chain of recursive calls.
o The anchor produces 1 as a result of raising x to the power of zero; the result is
passed back to the previous recursive call.

5
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

o Now, that call, whose execution has been pending, returns its result, x · 1 = x.
o The third call, which has been waiting for this result, computes its own result,
namely, x · x, and returns it.
o Next, this number x · x is received by the second call, which multiplies it by x and
returns the result, x · x · x, to the first invocation of power(). This call receives x ·
x · x, multiplies it by x, and returns the final result.
 In this way, each new call increases the level of recursion, as follows:

or alternatively, as

Tail Recursion
 All recursive definitions contain a reference to a set or function being defined. There are,
however, a variety of ways such a reference can be implemented.
 Tail recursion is characterized by the use of only one recursive call at the very end of a
method implementation.
 In other words, when the call is made, there are no statements left to be executed by the
method; the recursive call is not only the last statement but there are no earlier recursive
calls, direct or indirect.

6
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

 Tail recursive method has the recursive call as the last statement in the method.
 For example, the method tail() defined as below is an example of method with tail recursion
whereas nonTail() method is not.
void tail (int i) {
if (i > 0) {
System.out.print (i + "");
tail(i-1);
}
}
-----------------------------------------------------------
void nonTail (int i) {
if (i > 0) {
nonTail(i-1);
System.out.print (i + "");
nonTail(i-1);
}
}

Nontail Recursion
 Recursion that is not tail recursion.
int fact(int x){
if (x==0)
return 1;
else
return x*fact(x-1);
}
In this example, when returning back from a recursive call, there is still one pending
operation, multiplication. Therefore, fact is a non-tail recursive method

Assignment: Tail Recursion vs Nontail Recursion.

7
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

Indirect Recursion
 If a function calls itself indirectly via a chain of other calls then it is called indirect
recursion.
 The preceding sections discussed only direct recursion, where a method f( ) called itself.
However, f( ) can call itself indirectly via a chain of other calls. For example, f( ) can call
g( ), and g( ) can call f( ). This is the simplest case of indirect recursion.
 The chain of intermediate calls can be of an arbitrary length, as in:
f()  f1()  f2()  · · ·  fn()  f()

Nested Recursion
 Nested recursion a type of recursion in which a function is not only defined in terms of
itself, but also is used as one of the parameters.
 In this recursion, a recursive function will pass the parameter as a recursive call. That
means “recursion inside recursion”.
 The following definition is an example of such a nesting:

Function h has a solution for all n ≥ 0.

This fact is obvious for all n > 4 and n = 0, but it has to be proven for n = 1, 2, 3, and 4.
Thus,
h(2) = h(2 + h(4))
= h(2 + h(2 + h(8)))
= 12.
What are the values of h(n) for n = 1, 3, and 4?

8
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

Excessive Recursion
 Recursive algorithms tend to exhibit simplicity in their implementation and are typically
easy to read and follow
 However, this straightforwardness does have some drawbacks
o Generally, as the number of function calls increases, a program suffers from some
performance decrease
o Also, the amount of stack space required increases dramatically with the amount of
recursion that occurs
o This can lead to program crashes if the stack runs out of memory
 Logical simplicity and readability are used as an argument supporting the use of recursion.
 The price for using recursion is slowing down execution time and storing on the run-time
stack more things than required in a non recursive approach.
 If recursion is too deep then we can run out of space on the stack and our program
terminates abnormally by raising an unrecoverable StackOverflowError.
 If some recursive function repeats the computations for some parameters, the run time can
be prohibitively long even for very simple cases
 As an example of this consider Fibonacci numbers.
A sequence of Fibonacci numbers is defined as follows:

The definition states that if the first two numbers are 0 and 1, then any number in the
sequence is the sum of its two predecessors. But these predecessors are in turn sums of
their predecessors, and so on, to the beginning of the sequence.
 This tells us that that any Fibonacci number after the first two (0 and 1) is defined as
the sum of the two previous numbers
 However, as we move further on in the sequence, the amount of calculation necessary
to generate successive terms becomes excessive
 This is because every calculation ultimately has to rely on the base case for computing
the values, since no intermediate values are remembered

9
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

 The following algorithm implements this definition; again, notice the simplicity of the
code that belies the underlying inefficiency

int Fib (int n) {

if (n < 2)
return n;
else return Fib(n-2) + Fib(n-1);
}
o If we use this to compute Fib(6)(which is 8), the algorithm starts by calculating
Fib(4) + Fib(5)
o The algorithm then needs to calculate Fib(4) = Fib(2) + Fib(3), and finally the first
term of that is Fib(2) = Fib(0) + Fib(1)= 0 + 1 = 1
o The entire process can be represented using a tree to show the calculations:

Figure 2: The tree of calls for Fib(6).

 Counting the branches, it takes 25 calls to Fib( ) to calculate Fib(6)

 We can prove that the number of additions required to find Fib(n) using a
recursive definition is equal to Fib(n + 1) – 1.
 Counting two calls per one addition plus the very first call means that Fib( ) is
called 2 · Fib(n + 1) – 1 times to compute Fib(n).
 This number can be exceedingly large for fairly small ns, as the following table
indicates.

10
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

Figure 3: Number of addition operations and number of recursive calls to calculate Fibonacci

 It takes almost a quarter of a million calls to find the twenty-sixth Fibonacci number, and
nearly 3 million calls to determine the thirty-first! This is too heavy a price for the
simplicity of the recursive algorithm. As the number of calls and the run time grow
exponentially with n, the algorithm has to be abandoned except for very small numbers.

Backtracking
 In solving some problems, a situation arises where there are different ways leading from a
given position, none of them known to lead to a solution. After trying one path
unsuccessfully, we return to this crossroads and try to find a solution using another path.
However, we must ensure that such a return is possible and that all paths can be tried. This
technique is called backtracking.
 Backtracking is an approach to problem solving that uses a systematic search among
possible pathways to a solution
 As each path is examined, if it is determined the pathway isn’t viable, it is discarded and
the algorithm returns to the prior branch so that a different path can be explored
 Thus, the algorithm must be able to return to the previous position, and ensure that all
pathways are examined
 Using backtracking, we can always return to a position that offers other possibilities for
successfully solving the problem.
 Backtracking is used in a number of applications, including artificial intelligence,
compiling, and optimization problems.

11
Collected by Bipin Timalsina
 DSA with Java/Unit- 4

 One of the problems in which backtracking is very useful is the eight queens problem.
o The eight queens problem attempts to place eight queens on a chessboard in such a
way that no queen is attacking any other.
(The rules of chess say that a queen can take another piece if it lies on the same
row, on the same column, or on the same diagonal as the queen)

Figure 4: The eight queens problem

 The approach to solving this is to place one queen at a time, trying to make sure that the
queens do not check each other.
 If at any point a queen cannot be successfully placed, the algorithm backtracks to the
placement of the previous queen.
 This is then moved and the next queen is tried again.
 If no successful arrangement is found, the algorithm backtracks further, adjusting the
previous queen’s predecessor, etc.

12
Collected by Bipin Timalsina