Recursion
WHAT IS RECURSION.
W
W
e look at the concept of recursion, which is one of the very powerful programming concepts,
supported by most of the languages. At the same time, it is also a fact that most beginners are
confused by the way it works and are unable to use it effectively. Also, some languages may
not support recursion. In such cases, it may become necessary to rewrite recursive functions into non-
recursive ones. All these and many other aspects are dealt with in this chapter.
Recursion is an offshoot of the concept of subprograms. A subprogram as we know is the concept of
writing separate modules, which can be called from other points in the program or other programs. Then
came a concept wherein any subprogram can call any other subprogram. The control goes to the called
subprogram, performs the assigned tasks and comes back to the caller programs.
Then comes the question – can a program call itself? Theoretically it is possible. If so, where do we
use them normally? A subprogram is called to perform a function, which the caller subprogram cannot
perform itself. But if the caller program calls itself, what purpose does it serve? The answer is, the
subprogram no doubt, calls itself, but with a different value of the parameter. In fact, in most cases, the
calling continues until some specific value of the parameter is reached.
We now understand that recursion is a process of defining a process/ problem/ an object in terms of
itself. Recursion is one of the applications of stacks. The recursive mechanisms are extremely powerful,
but even more importantly; many times they can express an otherwise complex process, very clearly.
Any program can be written using recursion. Of course, the recursive program in that case could be
tougher to understand. Hence, recursion can be used when the problem itself can be defined recursively.
The general procedure for any recursive algorithm is as follows,
1. Save the parameters, local variables and return addresses.
BSIT 41 Algorithms
Chapter 5 - Recursion
2. If the termination criterion is reached perform final computation and go to step 3, otherwise
perform final computations and go to step 1.
3. Restore the most recently saved parameters, local variables and return address and go to the
latest return address.
5.2 WHY DO WE NEED RECURSION.
When iteration can be easily used and also supported by most programming languages, why do we
need recursion at all? The answer is that iteration has certain demerits as is made clear below:
1. Mathematical functions such as factorial and fibonacci series generation can be easily
implemented using recursion than iteration.
2. In iterative techniques looping of statement is very much necessary.
5.3 WHEN TO USE RECURSION.
Recursion can be used for repetitive computations in which each action is stated in terms of previous
result. There are two conditions that must be satisfied by any recursive procedure.
1. Each time a function calls itself it should get nearer to the solution.
2. There must be a decision criterion for stopping the process.
In making the decision about whether to write an algorithm in recursive or non-recursive form, it is
always advisable to consider a tree structure for the problem. If the structure is simple then use non-
recursive form. If the tree appears quite bushy, with little duplication of tasks, then recursion is suitable.
Recursion is a top down approach to problem solving. It divides the problem into pieces or selects out
one key step, postponing the rest. Whereas, iteration is more of a bottom up approach. It begins with what
is known and from this constructs the solution step by step.
Let us now look at some basic examples which are often devised using recursion.
5.4 FACTORIAL OF A POSITIVE INTEGE.
The factorial of a number ‘n’ = n * (n-1) * (n-2)* … * 3 * 2 * 1. An iterative way of obtaining the
factorial of a given number is to put a ‘for’ loop to repeat the multiplication n times. We start with 1, then
evaluate 1 * 2, then that product * 3, ….*(n-1). The factorial of a number can also be obtained recursively.
BSIT 41 Algorithms
Suppose we are asked to evaluate N!. If we somehow know (N-1)! then we can evaluate N! = N*(N1)!.
But how do we get (N-1)!? The same logic can be employed to evaluate (N-1)! = (N-1) * (N-2)!.
The problem of finding the factorial of a given number can be recursively defined as
*
-
.
1
Thus, the algorithm developed to compute the factorial of a given number is
Algorithm: Factorial
Input: n, the integer value whose factorial is to be computed
ìíî
Output: factorial of n
Method:
If (n==1) then
Return (1)
Else
Return (n * factorial (n-1)
If end
Algorithm ends
The students are advised to try various values of n to actually see how the method works.
5.5 FINDING THE NTH FIBONACCI NUMBE.
As already introduced in Chapter 3, a Fibonacci series is a sequence of integers 0,1,1,2,3,5…… i.e.,
The Fibonacci sequence starts from 0, 1 and after that each new term will be the sum of the previous two
terms. .We shall here, at finding out what could be the nth Fibonacci number in the series. For instance, if
we say the first Fibonacci number then it is 0. The second Fibonacci number is 1. Thus, if the 6th Fibonacci
number asked then we are expected to produce the number 5. In general, if kth Fibonacci number is
expected then that can be obtained by summing up (k-1)th and (k-2)th fibonacci numbers. This process
can be recursively done and finally one can obtain the kth Fibonacci number.
Thus, following is the recursive algorithm designed to find the nth Fibonacci number
Algorithm: Fibonacci
Input: n, the position at which the Fibonacci number has to be computed
Factorial
(
1)
if
1
n
n
n
Factorial (n) [where n is a positive integer] =
if n
1
=
Chapter 5 - Recursion
Output: nth Fibonacci number
Method:
If (n==0)
Return (0)
Else
If (n == 1)
Return (1)
Else
Return (Fibonacci (n-1) + Fibonacci (n-2))
If end
If end
Algorithm ends
Again, the correctness can be checked for various input values.
We use a third example, though normally this method is not used to explain recursion, nevertheless it is
a very useful method.
5.6 SUM OF FIRST N INTEGER.
The sum of the integers to n is the sum of the integers through n -1 + n. The sum of the integers to n
-1 is the sum to n -2 to n -1, etc. Eventually, we know that the sum of the first positive integer is 1.
Therefore, we can define a terminating condition for some small subset of the problem. The recursive
algorithm to achieve this is as follows
Algorithm : SumPosInt
Input : n, the upper limit
Output : Sum of first n positive integers
Method:
if (n <= 0) // We only want positive integers
return 0;
BSIT 41 Algorithms
else
if (n == 0) // Our terminating condition
return 1;
else
return (n + SumPosInt( n -1 ); // recursive step
if end
if end
Algorithm ends
5.7 BINARY SEARC.
Binary search method as explained earlier is a process of searching for the presence or absence of a
key element in the sorted list. The approximate mid entry is located and its key value is examined. If the
mid value is greater than X, then the list is chopped off at the (mid-1)th location. Now the list gets reduced
to half the original list. The middle entry of the left-reduced list is examined in a similar manner. Thus, one
can always think of using a recursive algorithm to solve the same.
The recursive algorithm for binary search is as follows,
Algorithm : binary search
Input : A, vector of n elements
K, search element
Low, the lower limit
High, the upper limit //initially low=1 and high=n the number of elements
Output : the position of the K
Method : if (low <= high)
mid=(low+high)/2
if( a[mid] == K)
return(mid)
else
Chapter 5 - Recursion
if (a[mid]< K)
Binary search(A, K, Low, mid)
else
Binary Search(A, K, High, mid)
if end
if end
else
return(0)
if end
Algorithm ends.
5.8 MAXIMUM AND MINIMUM IN THE GIVEN LIST OF .
ELEMENT.
Here the problem is to find out the maximum values in a give list of n data elements. The recursive
algorithm designed to serve this purpose is as follows.
Algorithm: Max-Min
Input: p, q, the lower and upper limits of the dataset
max, min, two variables to return the maximum and minimum values in the list
Output: the maximum and minimum values in the data set
Method:
If (p = q) Then
max = a(p)
min = a(q)
Else
If ( p – q-1) Then
If a(p) > a(q) Then
BSIT 41 Algorithms
max = a(p)
min = a(q)
Else
max = a(q)
min = a(p)
If End
Else
m ¬ (p+q)/2
max-min(p,m,max1,min1)
max-min(m+1,q,max2,min2)
max f large(max1,max2)
min fsmall(min1,min2)
If End
If End
Algorithm Ends.
5.9 MERGE SOR.
Sorting as stated in Chapter 4, is a process of arranging a set of given numbers in some order. The
basic concept of merge sort is like this. Consider a series of n numbers, say A(1), A(2) ……A(n/2) and
A(n/2 + 1), A(n/2 + 2) ……. A(n). Suppose we individually sort the first set and also the second set. To
get the final sorted list, we merge the two sets into one common set.
We first look into the concept of arranging two individually sorted series of numbers into a common
series using an example:
Let the first set be A = {3, 5, 8, 14, 27, 32}. Let the second set be B = {2, 6, 9, 15, 18, 30}.
The two lists need not be equal in length. For example the first list can have 8 elements and the second
5. Now we want to merge these two lists to form a common list C. Look at the elements A(1) and B(1),
A(1) is 3, B(1) is 2. Since B(1) < A(1), B(1) will be the first element of C i.e., C(1)=2. Now compare
A(1) =3 with B(2) =6. Since A(1) is smaller then B(2), A(1) will become the second element of C. C[ ]
= {2, 3}
Chapter 5 - Recursion
Similarly compare A(2) with B(2), since A(2) is smaller, it will be the third element and so on. Finally,
C is built up as C[ ]= {2, 3, 5, 6, 8, 9, 14, 15, 18, 27, 30, 32}.
However the main problem remains. In the above example, we presume that both A & B are originally
sorted. Then only they can be merged. But, how do we sort them in the first? To do this and show the
consequent merging process, we look at the following example. Consider the series A= (7 5 15 6 4). Now
divide A into 2 parts (7, 5, 15) and (6, 4). Divide (7, 5, 15) again as ((7, 5) and (15)) and (6, 4) as ((6) (4)).
Again (7, 5) is divided and hence ((7, 5) and (15)) becomes (((7) and (5)) and (15)).
Now since every element has only one number, we cannot divide again. Now, we start merging them,
taking two lists at a time. When we merge 7 and 5 as per the example above, we get (5, 7) merge this with
15 to get (5, 7, 15). Merge this with 6 to get (5, 6, 7, 15). Merging this with 4, we finally get (4, 5, 6, 7 and
15). This is the sorted list.
You are now expected to take different sets of examples and see that the method always works.
We design two algorithms in the following. The main algorithm is a recursive algorithm (some what
similar to the binary search algorithm that we saw earlier) which calls at times the other algorithm called
MERGE. The algorithm MERGE does the merging operation as discussed earlier.
Algorithm: MERGESORT
Input: low, high, the lower and upper limits of the list to be sorted
A, the list of elements
Output: A, Sorted list
Method:
If (low<high)
mid¬ (low + high)/2
MERGESORT(low, mid)
MERGESORT (mid, high)
MERGE(A, low, mid, high)
If end
Algorithm ends
You may recall that this algorithm runs on lines parallel to the binary search algorithm. Each time it
divides the list (low, high) into two lists(low, mid) and (mid+1, high). But later, calls for merging the two
lists.
BSIT 41 Algorithms
Algorithm: Merge
Input: low, mid, high, limits of two lists to be merged i.e., A(low, mid) and A(mid+1, high)
A, the list of elements
Output: B, the merged and sorted list
Method:
h = low, i = low, j = mid + 1;
While ((h dŠ mid) and (j dŠ high)) do
If (A(h) dŠ A(j) )
B(i) = a(h);
h = h+1;
else
B(i) = A(j);
j = j+1;
If end
i = i+1;
If (h > mid)
For k = j to high
B(i) = A(k);
i = i+1;
For end
Else
For k = h to mid
B(i) = A(k);
i = i+1
For end
If end
While end
Algorithm ends
Chapter 5 - Recursion
The first portion of the algorithm works exactly similar to the explanation given earlier, except that
instead of using two lists A and B to fill another array C, we use the elements of the same array A[low,mid]
and A[mid+1,high] to write into another array B.
Now it is not necessary that both the lists from which we keep picking elements to write into B should
get exhausted simultaneously. If the fist list gets exhausted earlier, then the elements of the second list are
directly written into B, without any comparisons being needed and vice versa. This aspect will be taken
care of by the second half of the algorithm.
5.10 QUICKSOR.
This is another method of sorting that uses a different methodology to arrive at the same sorted result.
It “Partitions” the list into 2 parts (similar to merge sort), but not necessarily at the centre, but at an
arbitrarily “pivot” place and ensures that all elements to the left of the pivot element are lesser than the
element itself and all those to the right of it are greater than the element. Consider the following example.
75 80 85 90 95 70 65 60 55
To facilitate ordering, we add a very large element, say 1000 at the end. We keep in mind that this is
what we have added and is not a part of the list.
75 80 85 90 95 70 65 60 55 1000
A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9) A(10)
Now consider the first element. We want to move this element 75 to its correct position in the list. At
the end of the operation, all elements to the left of 75 should be less than 75 and those to the right should
be greater than 75. This we do as follows:
Start from A(2) and keep moving forward until an element which is greater than 75 is obtained.
Simultaneously start from A(10) and keep moving backward until an element smaller than 75 is obtained.
A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8) A(9) A(10)
75 80 85 90 95 70 65 60 55 1000
Now A(2) is larger than A(1) and A(9) is less than A(1). So interchange them and continue the
process.
75 55 85 90 95 70 65 60 80 1000
Again A(3) is larger than A(1) and A(8) is less than A(1), so interchange them.
75 55 60 90 95 70 65 85 80 1000
Similarly A(4) is larger than A(1) and A(7) is less than A(1), interchange them
BSIT 41 Algorithms
75 55 60 65 95 70 90 85 80 1000
In the next stage A(5) is larger than A(1) and A(6) is lesser than A(1), after interchanging we have
75 55 60 65 70 95 90 85 80 1000
In the next stage A(6) is larger than A(1) and A(5) is lesser than A(1), we can see that the pointers
have crossed each other, hence Interchange A(1) and A(5).
70 55 60 65 75 95 90 85 80 1000
We have completed one series of operations. Note that 75 is at its proper place. All elements to its left
are lesser and to it’s right are greater.
Next we repeat the same sequence of operations from A(1) to A(4) and also between A(6) to A(10).
This we keep repeating till single element lists are arrived at.
Now we suggest a detailed algorithm to do the same. As before, two algorithms are written. The
main algorithm, called QuickSort repeatedly calls itself with lesser and lesser number of elements. However,
the sequence of operations explained above is done by another algorithm called PARTITION
Algorithm: QuickSort
Input: p, q, the lower and upper limits of the list of elements A to be sorted
Output: A, the sorted list
Method:
If (p < q)
j = q+1;
PARTITION (p, j)
QuickSort(P, j-1)
Quicksort(j+1, q)
If end
Algorithm ends
Algorithm: PARTITION
Input: m, the position of the element whose actual position in the sorted list has to be found
p, the upper limit of the list
Output: the position of mth element
Chapter 5 - Recursion
Method:
v = A(m);
i = m;
Repeat
Repeat
i = i+1
Until (A(i) e> v);
Repeat
p = p - 1
Until (A(p) d” v);
If (i < p)
INTERCHANGE(A(i), A(p))
If end
Until (i e” p)
A(m) = A(p) ;
A(p) = v;
Algorithm ends
5.11 DEMERITS OF RECURSIO.
Now, are you thinking that recursion is the best programming technique to be followed? Well, you are
wrong. Recursion has some demerits too, which often make it a not-so-favoured solution to a problem.
Some of the demerits of recursive algorithms are listed below:
1. Many programming languages do not support recursion; hence recursive mathematical function
is implemented using iterative methods.
2. Even though mathematical functions can be easily implemented using recursion it is always at
the cost of execution time and memory space.
BSIT 41 Algorithms
Fig. 5.1 Time Space tree of the algorithm Fibonacci
For example, the recursion tree for generating 6 numbers in a fibonacci series generation is given in fig
5.1. A fibonacci series is of the form 0,1,1,2,3,5,8,13…etc, where the third number is the sum of preceding
two numbers and so on. It can be noticed from the fig 5.1 that, f (n-2) is computed twice, f (n-3) is
computed thrice, f (n-4) is computed 5 times.
3. A recursive procedure can be called from within or outside itself and to ensure its proper
functioning it has to save in some order the return addresses so that, a return to the proper
location will result when the return to a calling statement is made.
4. The recursive programs needs considerably more storage and will take more time.
SUMMAR.
In this chapter, the concepts of recursion are introduced. Some simple problems which were discussed
in the earlier chapters are reconsidered and the recursive algorithms are designed to achieve the same
outcome. Two sorting algorithms namely Quick sort and merge sort are presented and the recursive
algorithms are designed.
EXERCIS.
1. Trace out the algorithm Merge Sort on the data set {1,5,2,19,4,17, 45, 12, 6}
2. Trace out the algorithm Quick Sort on the data set {12 , 1, 5,7,19,15, 8, 9, 10}
3. Implement all the algorithms designed in this chapter.
4. Trace out the algorithm MaxMin on a data set consisting of atleast 8 elements.
5. List out the merits and demerits of Recursion.
6. The data structure used by recursive algorithms is _____________
7. When is it appropriate to use recursion?
