Data Structures with Algorithms 22MCA13

Module -2: Recursion and Queue

Module-2: Recursion and Queue

• Recursion:

- Factorial

- GCD

- Fibonacci Sequence

- Tower of Hanoi

• Queue:

- Definition

- Representation

- Operations

- Queue Variants:

o Circular Queue.

o Priority Queue,

o Double Ended Queue

- Applications of Queues.

- Programming Examples.

1
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

1. Recursion
I

• Definition
Recursion is a process of solving a problem by reducing the given problem into smaller
version of the same problem.
or
Recursion is a technique that solves a problem by dividing a problem into smaller
problem of the same type.
Recursive function:
Function which calls or invokes itself again and again until certain condition is reached
is called as a recursive function.

• Advantages
1. Recursive solutions are shorter and simpler.
2. Code is easier to use.
3. Follows divide and conquer to solve problems.

• Disadvantages:
4. Recursion is difficult concept to some programmers.
5. Recursion uses system stack. If the system stack is limited, it is difficult to
implement recursion.
6. Uses more memory and time to execute.
7. It is difficult to find errors.

In general,

Recursion is a process by which we define something in terms of itself. In Latin, Re - means

back and Currere- means to run.

A procedure or function that is run over and over for a definite number of times is recursion.

Many problems - Factorial, GCD, Fibonacci, Tower of Hanoi, etc. - use recursive technique
to solve. This approach is useful for both the definition of mathematical functions
(recurrence relation) and for the definition of data structure.

2
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

The following problems are solved using Recursion:

- Factorial

- GCD

- Fibonacci Sequence

- Tower of Hanoi

3
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Factorial of a Number

In Mathematics, factorial is an important function, which is used to find how many ways things
can be arranged or the ordered set of numbers. The well-known interpolating function of the
factorial function was discovered by Daniel Bernoulli. In short, a factorial is a function, that
multiplies a number by every number below it.

What is Factorial?
In Mathematics, Factorials are just products. An exclamation (!) mark indicates the factorial.
Factorial is a multiplication operation of natural numbers with all the natural numbers that are
less than it.

Factorial Notation
The multiplication of all positive integers says "n", that will be smaller than or equivalent to n is
known as the factorial. The factorial of a positive integer is represented by the symbol "n!".

Factorial Formula
The formula to find the factorial of a number is: n! = n * (n-1) * (n-2) * (n-3) *……* 3 * 2 * 1

What About ”0!”

Zero Factorial is interesting ... it is generally agreed t at O! = 1.

It may seem funny that multiplying no numbers together results in 1, but let's follow the pattern
backwards from, say, 4! like this:

41 = 24
31 = 6
2! = 2
1! = 1
0! = 1
And in many equations using O! = 1 just makes sense.

• Factorial of a Number
Recursive definition:
- factorial (n) = 1 if n=O or n =1
- factorial (n) = n * factorial (n-1) if n>l

4
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Where is Factorial
Used? Example:1
Example: how many ways can we arrange letters (without repeating)?
For 1 letter "a" here is only 1 way: a
For 2 letters "ab" there are 1X2=2 ways: ab, ba
For 3 letters "abc" there are 1X2X3=6 ways: abc acb cab bac bca cba
For 4 letters "abed" there are 1x2x3x4=24 ways: (try it yourself!)
etc

The formula is simply n!

Now ... how many ways can we arrange no letters? Just one way, an empty space: So O! =1

5
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Ql. Write C program to find factorial of a number using recursion

#include<stdio.h>
#include<conio.h>

long int fact (int n )

{
If(n == 0 || n==1)
return 1;
return n * fact(n -1);
}

void main()
{
int n;
long int result;

//clrscr();

printf ("Enter the Number:");

scanf ( "%d", &n);

result= fact(n );

printf ("%d! = %ld", n, result);

//getch();
}
Output:

6
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

1.2. GCD of a Number

The Greatest Common Divisor of two integers a and b, not both zero, is the largest of the
common divisors of a and b. It is denoted as gcd (a, b).

What is common divisor?

If d is a divisor of a and also a divisor of b, then d is a common divisor of a and b.

Example 1: Find the Greatest Common Divisor of 12 and 16

The Greatest Common Divisor of 12 and 16 is:

GCD (12, 16) = 4

Example 2: Find the Greatest Common Divisor of 12 and

30

List the Different methods is used to find GCD of two numbers.

GCD: Greatest Common Divisor

"Largest integer [Common Divisor] that divide both numbers evenly; with remainder zero".

Different methods to find GCD of two numbers:

i) Euclid's algorithm: Uses Modulus method.

ii)Consecutive integer checking.
iii) Middle school procedure.
iv) Repetitive subtraction method.

7
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Q2. Write C program to find GCD of two numbers using Euclidean method and recursion
#include<stdio.h>

int gcd_algorithm(int a, int b)

{
int x = (a > b) ? a : b; // a is greater number
int y = (a < b) ? a : b; // b is smaller number

if (y == 0)
{
return x;
}
else
{
return gcd_algorithm(y, (x % y));
}
}

int main()
{
int num1, num2, gcd;
printf("\nEnter two numbers to find gcd using Euclidean algorithm:
");
scanf("%d%d", &num1, &num2);
gcd = gcd_algorithm(num1, num2);

printf("The GCD of %d and %d is %d\n", num1, num2, gcd);

return 0;
}

8
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

9
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

1.3. Fibonacci Sequence

1
0
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

• Fibonacci Series
Recursive definition:
- fib(n) = n if n=O or n
- fib(n) = fib(n-2)+fib(n-1) =1 if n>=2

Q4. Write C program to print Fibonacci series for n terms using recursion
#include <stdio.h>
#include <conio.h>

int fib (int n)

{
if(n==0){
return 0;
}
else if(n==1)
return 1;
else
return fib(n-2)+fib(n-1);
}
void main()
{
int n,i;
//clrscr();

printf("\n Enter the number of Terms ");

scanf( "%d", &n);

for(i=0; i<n; i++)

printf(" %d ", fib(i) );

getch();
}
Output:

1
1
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective

of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and placing it on top

of another stack i.e., a disk can only be moved if it is the uppermost disk on a stack.

3. No disk may be placed on top of a smaller disk.

Example for 3 disks:

Image illustration for 3 disks:

1
2
 Data Structures with Algorithms 20MCA11
Module -2: Recursion and Queue

QS. Write C program for tower of Hanoi using recursion

II solve tower of hanoi
puzzle #include <stdio.h>
#include<conio.h>

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)

{
if ( n == 1)
{
printf( "\nMove disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
printf("\nMove disk %d from rod %c to rod %c ", n, from_rod, to_rod);
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

void main()
{
int n; II Number of

disks

printf("Enetr number of Disks:");

scanf( "%d", &n);

printf{"\nTower of Hanoi Solution for %d disks:\n",n);

towerOfHanoi(n, 'A', ‘C’, 'B');

II A, Band Care names of rods

Output:

13
 Data Structures with 22MCA13
Module -2: Recursion andAlgorithms
Queue

[Link]

Queue:
Definition

Representation

Operations

Queue Variants:

Circular Queue,

Priority Queue,
Double Ended Queue
Applications of Queues.

Programming Examples.

14
 Data Structures with 22MCA13
Module -2: Recursion andAlgorithms
Queue

2.1 Queue or Ordinary Queue

• Definition

"A Queue is a Linear collection of list in which insertion and deletions takes place at
different ends. The end at which insertion takes place is called the rear end and at end at
which deletions takes place is called the front end".

• Queue memory Representation and Operations on Queue

• Properties of Queue:

- Queue is an abstract data type with a predefined capacity.

- Queue uses FIFO structure (First in - First out)
- FIFO list (First in first out)- the element entered first is removed first.
- Queue is an ordered list of similar data type.

• Basic Queue operations

- enqueue(): Insert item at rear of queue

- dequeue(): remove an item from front of queue
- display() : display the elements in queue
- isfull() : returns true if queue is full.
- isempty() : returns true if queue is empty.

15
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

• enqueue() : Insert item at rear of queue.

• dequeue(): remove an item from front of queue

• Queue Variants / Types:

1. Linear Queue

2. Circular Queue

3. Priority Queue

4. Double Ended Queue

16
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Linear Queue or Queue

It is also known as ordinary or simple queue.

Inserting an element at the REAR end

 Check if the queue is full.

 For the first element, set the value of front to 0.
 Increase the REAR index by 1
 Add the new element in the position pointed by REAR.

C function to insert an element at the REAR end

void insert_rearQ()
{
if (rear == SIZE-1)
{
printf( "\n ** Queue is Overflow** \n");
}
else
{
if (front==-1)
{
front=0;
}
printf("Enter the element to be inserted into queue:");
scanf("%d", &ele);
rear++;
Q[rear]=ele;
printf("\n Inserted -> %d", ele);
}
}

17
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Deleting an element from the FRONT end

 Check if the queue is empty

 Return the value pointed by FRONT
 Increase the FRONT index by 1
 For the last element, reset the values of FRONT and REAR to -1

C function to delete element from FRONT

void delete_frontQ()
{
if (front==-1)
{
printf ("**Queue is Underflow **\n");
}
else
{
printf("\n Deleted item is: %d \n", Q[front]);
front++;
if(front>=rear){
front=rear=-1;
}
}
}

C function to print the queue elements

void display( )
{
int i;
if(rear==-1)
{
printf("\n ** Queue is Empty...\n");
}
printf(" Queue elements are:\n");
for(i=front; i<= rear; i++)
printf("\n%d ", Q[i]);
}

18
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Q7. Write a C program to demonstrate the Queue operations. Display appropriate messages
as Queue Overflow and Queue Underflow. enqueue(), dequeue(), display()

/* Queue Implementation */
#include<stdio.h>
#include<stdlib.h>

# define SIZE 3
int Q[SIZE], choice, ele;

int front=-1;
int rear=-1;

void insert_rearQ(); //enqueue()

void delete_frontQ();//dequeue()
void display();

int main(){

printf("\n Queue Operations Using Arrays");

printf("\n -----------------------------");
printf("\n [Link] in Rear\n [Link] from Front\n [Link]\n [Link]");

while(1)
{
printf("\nEnter your choice:\n ");
scanf("%d", &choice);
switch(choice)
{
case 1:
/* Insert an item/element in queue */
insert_rearQ();
break;

case 2:
{
/* Remove an item from queue */
delete_frontQ;
break;
}
case 3:
{
display();
break;
}
case 4:
exit(0);

19
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

default:{
printf("\n Please Enter a Valid Choice ( 1/2/3/4)");
}

}
}
}

/* function for Inserting an element -> enqueue */

void insert_rearQ()
{
if (rear == SIZE-1)
{
printf( "\n ** Queue is Overflow** \n");
return;
}
else
{
if (front==-1)
{
front=0;
}
printf("Enter the element to be inserted into queue:");
scanf("%d", &ele);
rear++;
Q[rear]=ele;
printf("\n Inserted -> %d", ele);
}
}
//dequeue -> function for deleting element
void delete_frontQ()
{
if (front==-1)
{
printf ("**Queue is Underflow **\n");
}
else
{
printf("\n Deleted item is: %d \n",Q[front]);
front++;
if(front>=rear){
front=rear=-1;
}
}}

void display( )
{
20
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue
int i;
if(rear==-1)
{
printf("\n ** Queue is Empty...\n");
}
printf(" Queue elements are:\n");
for(i=front; i<= rear; i++)
printf("\n%d ", Q[i]);
}

Output:

21
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

• Disadvantages of ordinary/Simple Queue:

A major disadvantage of a classical queue is that a new element can only be

inserted when all the elements are deleted from the queue.

As an example, consider the queue:

Now, if the first three members are de-queued (deleted/removed) from the front

(left hand side) of the queue, we get:

Where the queue remains full, but we cannot insert a new element because the

back of the queue (right hand side) remains as it was before. This is the major

limitation of a classical queue, i.e., even if there is space available at the front of the

queue, we cannot use it and its unnecessary wastage of memory.

So, to overcome the problem above, we can use a circular queue.

22
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Circular Queue

• Definition

"Circular queue is a linear data structure where the last node is connected back to the first
node to make a circle. Elements are added at the rear end and the elements are deleted at
front end of the queue".

• Circular Queue memory Representation and Operations on Queue

Figure: Circular Queue representation and operations

• Properties of Circular Queue:

- In circular queue the last node is connected back to the first node to make a circle.
- Circular linked list fallows the First In First Out principle.
- Elements are added at the rear end and the elements are deleted at front end of
the queue.
- Both the front and the rear pointers points to the beginning of the array.
- It is also caIled as "Ring buffer".

23
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

QS. Implement circular queue Using C program.

/* implementation of circular queue. */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
# define max 3

int CQ[max];
int front=0, rear=-1, count=0;

void insert(int item)

{
if(count == max)
{
printf("\nCQ is overflow!!!\n");
return;
}
count++;
rear=(rear+1)%max;
CQ[rear]=item;
printf("\nElement %d inserted\n",item);
}

void del()
{
int item;

if(count == 0)
{
printf("\nCQ is underflow!!!\n");
return;
}
count--;
item= CQ[front];
front= (front+1) % max;

24
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

printf("\nDeleted Element is %d\n",item);

}

void display()
{
int i,f;

if(count == 0)
{
printf("\nCQ is Empty!!!\n");
return;
}
f = front;
printf("\nCQ elements are:");
for(i=1; i<=count; i++)
{
printf("\n%d",CQ[f]);
f = (f + 1) % max;
}
printf("\n");
}

void main()
{
int ch, item;
//clrscr();

while(1)
{
printf("\n 1:Insert Rear\n 2:Delete Front\n 3:Display\n 4:Exit\n");

printf("\nEnter your Choice:");

scanf( "%d", &ch);

switch(ch)
25
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

{
case 1:
printf("\nEnter an item to insert:");
scanf("%d",&item);
insert(item);
break;

case 2:
del();
break;

case 3: display();
break;

case 4: exit(0);
break;

default:
printf("Invalid choice!!!");
break;
}
//getch();
}
}

Output:

26
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Priority Queue

• Definition

"Priority Queue is an extension of queue with following properties."

1. Every item has a priority associated with it.
2. An element with high priority is enqueued or dequeued before an element with low
priority.
3. If two elements have the same priority, they are served according to their order in
the queue.

Q9. Write a C program to Implement Priority queue using structure.

/*implementation of priority queue. */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

#define MAX 3
#define n 3

typedef struct
{
int items[MAX];
int front;
int rear;
}QUEUE;

void qinsert(QUEUE q[],int p,int elem)

{
if(q[p].rear==MAX-1)
{
printf("\n Queue %d - overflow\n",p+1);
return;
}

q[p].rear++;
q[p].items[q[p].rear] = elem;

if(q[p].front == -1)
q[p].front=0;

27
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

int qdelete(QUEUE q[])

{
int temp=-1;
int empty,p;

for(p=0;p<n;p++)
{
if(q[p].front != -1)
{
temp=q[p].items[q[p].front];
if(q[p].front==q[p].rear)
q[p].front=q[p].rear=-1;
else
q[p].front++;
break;
}
}
return temp;
}

void main()
{
QUEUE q[n];
int i,elem,ch,pri;
int item;
//clrscr();

for(i=0;i<n;i++)
q[i].front = q[i].rear = -1;

while(1)
{
printf("------------------- ");
printf("\n\[Link]\n\t2 Display\n\t3 Delete\n\t4 Exit\n");
printf("------------------- ");

printf( "\nEnter Your Choice: ");

scanf("%d",&ch);
switch(ch)
{ case 1 :
printf("\n Enter priority from 1 to 3:");
scanf("%d",&pri);
printf("\n Enter item:");

28
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

scanf("%d",&elem);

qinsert(q,pri-1,elem);
break;
case 2:
for(pri=0;pri<n;pri++)
{
printf("\n Priority :%d\n",pri+1);
for(i=q[pri].front;(i<=q[pri].rear)&&(i>=0);i++)

printf(" %d",q[pri].items[i]);
printf("\n");
}

break;

case 3 :
item= qdelete(q);
if(item==-1)
printf("\n Queue is empty and Q is UNDERFLOW\n");
else
printf("\n Deleted element %d\n",item);
break;

default :
printf("\n Invalid option\n");
exit(0);
break;
}
}
}

29
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

I 2.4 Double Ended Queue

• Definition

"Double-ended queue is an abstract data type for which elements can be added to or
removed from either the front or rear end".
- New items can be added at either the front or the rear and existing items can be
removed from either the front or the rear end.
- It is also often called as a deque or head-tail linked list.

• Memory representation

REAR/FRONT FRONT/REAR
Figure: Double Ended Queue representation and operations

• Properties

- Iteration over elements can be performed in any order.

- Elements can be efficiently added or removed from any end easily.

30
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue
• Basic Double Ended Queue operations

• Insert an element at REAR end

• Insert an element at FRONT end
• Delete an element at REAR end
• Delete an element at FRONT end
• Display the elements

• Types of deque

1. Input-restricted deque:
Where deletion can be made from both ends, but insertion can be made at only one end.

2. Output-restricted deque:
Where insertion can be made at both ends, but deletion can be made from only one end.

QlO. Write a C program to Implement Double Ended queue using structure.

/*implementation of double ended queue. */

#include<stdio.h>
#include<process.h>
#define MAX 30

typedef struct dequeue

{
int
data[MAX]; int
rear,front;
}dequeue;

void initialize(dequeue *p);

int empty(dequeue *p);
int full(dequeue *p);
void enqueueR(dequeue *p,int x);
31
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue
void enqueueF(dequeue *p,int
x); int dequeueF(dequeue *p);
int dequeueR(dequeue *p);
void print(dequeue *p);

void main()
{
int i,x,op,n;
dequeue q;

initialize(&q);

do
{

printf("\[Link]\[Link](rear)\[Link](front)\[Link](rear)
\[Link](front)"); printf("\[Link]\
[Link]\n\nEnter your choice:"); scanf("%d",&op);

switch(op)
{
case 1: printf("\nEnter number of elements:");
scanf("%d",&n);
initialize(&q); printf("\
nEnter the data:");

for( i=0;i<n;i++)
{
scanf("%d",&x);
if(full(&q))
{
printf( "\nQueue is full!!");
exit(0);
}
enqueueR(&q,x);
}
break;

case 2: printf("\nEnter element to be inserted:");

scanf("%d",&x);

if(full(&q))
{
printf("\nQueue is full!!");
exit(0);
}

enqueueR(&q,x);
break;
32
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue
case 3: printf("\nEnter the element to be inserted:");
scanf("%d",&x);

if(full(&q))
{
printf( "\nQueue is full!!");
exit(0);
}

enqueueF(&q,x);
break;

case 4: if(empty(&q))
{
printf("\nQueue is empty!!");
exit(0);
}

x=dequeueR(&q);
printf("\nElement deleted is %d\n",x);
break;

case 5: if(empty(&q))

printf("\nQueue is empty!!");
exit(0);
}

x=dequeueF(&q);
printf("\nElement deleted is %d\n",x);
break;

case 6: print(&q);
break;

default: break;
}
}while(op!=7);
}

void initialize(dequeue *P)

{
P->rear=-1;
P->front=-1;
}

33
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

int empty(dequeue *P)

{
if(P->rear==-1)
return(l);

return(0);
}

int full(dequeue *P)

{
if((P->rear+1)%MAX==P->front)
return(l);

return(0);
}

void enqueueR(dequeue *P,int x)

{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->rear=(P->rear+1)%MAX;
P->data[P->rear]=x;
}
}

void enqueueF(dequeue *P,int x)

{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->front=(P->front-l+MAX)%MAX;
P->data[P->front]=x;
}
}

34
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

int dequeueF(dequeue *P)

{
int x;

x=P->data[P->front];

if(P->rear==P->front) //delete the last element

initialize(P);
else
P->front=(P->front+1)%MAX;

return(x);
}

int dequeueR(dequeue *P)

{
int x;

x=P->data[P->rear];

if(P->rear==P->front)
initialize(P);
else
P->rear=(P->rear-l+MAX)%MAX;

return(x);
}

void print(dequeue *P)

{
int i;
if(empty(P))
{
printf("\nQueue is empty!!");
exit(0);
}

i=P->front;

while(i!=P->rear)
{
printf("\n%d",P->data[i]);
i=(i+1)%MAX;
}

printf("\n%d\n",P->data[P->rear]);
}

35
 Data Structures with Algorithms 22MCA13
Module -2: Recursion and Queue

Recursion

1 What is recursion? Write a recursive function for binary search. 6

2 C program to Reverse a Sentence Using Recursion 6

3 Write a recursive Program to Find the greatest common deviser of two integers. 6

4 C Program to Find the Factorial of a Number Using Recursion 6

5 C program to Calculate the Power of a Number Using Recursion 6

6 What is recursion? Write a recursive function for tower of Hanoi problem.

Queue

1 Write a function in C to simulate the working of linear queue for the following 8
operations.
i) insert ii) delete iii) display.
2 What is the need for using circular array to implement queues? 4
3 List the applications of liner queue. Implement insert and delete operations. 8
4 What is circular queue 8
Write C function to implement circular queue
a) insert front b) remove front c) display list

5 Write algorithms to insert into and delete elements from a doubly ended queue 8
6 List the applications of Stack and Queue. 4
7 What is Deque? 4
8 What is priority queue? Explain about different types of priority queue. 5

36