Data Structures and Algorithms Lab

Recursion:

The process in which a function calls itself directly or indirectly is called

recursion and the corresponding function is called a recursive function.

Recursion is an amazing technique with the help of which we can reduce the

length of our code and make it easier to read and write.

 Performing the same operations multiple times with different inputs.

 In every step, we try smaller inputs to make the problem smaller.

 Base condition is needed to stop the recursion otherwise infinite loop

will occur.

(1) Write a Program to find GCD of two given integers using Recursive

Function:

#include<stdio.h>

int gcd (int a, int b)

if (b==0)

return a;

else

return gcd(b, a%b);

int main()

int a, b, g;
 printf(“Enter two numbers:”);

scanf(“%d%d”, &a, &b);

g = gcd(a, b);

printf(“GCD is %d”, g);

return 0;

OUTPUT:

Enter two numbers: 10 18

GCD is 2

(2) Write a program to find Nth Fibonacci Number using recursive

function.

#include<stdio.h>
int fib(int n)
{
if(n==1 || n==2)
return (n-1);
else
return fib(n-1) + fib(n-2);
}
int main()
{
int n, t;
printf(“Enter a number:”);
scanf(“%d”, &n);
t = fib(n);
printf(“Nth term is %d”, t);
 return 0;
}

OUTPUT:

Enter a number: 8
Nth term is 13

(3) Write a program for Towers of Hanoi using recursion: N disks are

to be transferred from Peg S to Peg D with Peg I as the intermediate

Peg.

#include<stdio.h>
void toh(char src, char aux, char dst, int n)
{
if(n == 0)
return;
else
{
toh (src, dst, aux, n-1);
printf (“Move disc %d from %c to %c\n", n, src, dst);
toh (aux, src, dst, n-1);
}
}
int main()
{
int n;
printf("Enter number of disks:");
scanf("%d", &n);
toh('A', 'B', 'C', n);
return 0;
}

OUTPUT:
 Enter number of disks: 3

Move disc 1 from A to C

Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C

Searching:

The process of finding the desired information from the set of items stored in

the form of elements in the computer memory is referred to as Searching.

(4) Write a program to find an element in given list of elements using

Linear Search

In Linear Search Algorithm,

 Every element is considered as a potential match for the key and

checked for the same.

 If any element is found equal to the key, the search is successful and

the index of that element is returned.

 If no element is found equal to the key, the search yields “No match

found”.

#include<stdio.h>

int linearsearch(int a[], int n, int key)

{
 int i;

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

if(key == a[i])

return (i+1);

return -1;

int main()

int i, n, key, pos, a[30];

printf(“Enter the range:”);

scanf(“%d”, &n);

printf(“Enter %d elements”, n);

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

scanf(“%d”, &a[i]);

printf(“Enter the key element: “);

scanf(“%d”, &key);

pos = linearsearch(a, n, key);

if(pos != -1)

printf(“Element found at position %d”, pos);

else

printf(“Element not found”);

return 0;

OUTPUT:

Enter the range: 5

Enter 5 elements: 5 2 4 1 3

Enter the key element: 1

 Element found at position 4

(5) Write a program to find an element in given list of elements using

Binary Search

In this algorithm,

 Divide the search space into two halves by finding the middle index
“mid”.

 Compare the middle element of the search space with the key.

 If the key is found at middle element, the process is terminated.

 If the key is not found at middle element, choose which half will be
used as the next search space.

 If the key is smaller than the middle element, then the left side
is used for next search.

 If the key is larger than the middle element, then the right side
is used for next search.

 This process is continued until the key is found or the total search
space is exhausted.

#include<stdio.h>

int binarysearch(int a[], int n, int key)

int low, high, mid;

low = 0;

high = n-1;

while(low <=high)

mid = (low+high)/2;

if(a[mid] == key) return (mid+1);

else if(a[mid] < key) low = mid+1;

else high = mid-1;

return -1;

int main()

int i, n, key, pos, a[30];

printf(“Enter the range:”);

scanf(“%d”, &n);

printf(“Enter %d elements in ascending order”, n);

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

scanf(“%d”, &a[i]);

printf(“Enter the key element: “);

scanf(“%d”, &key);

pos = binarysearch(a, n, key);

if(pos != -1)

printf(“Element found at position %d”, pos);

else

printf(“Element not found”);

return 0;

OUTPUT:

Enter the range: 5

Enter 5 elements: 1 2 3 4 5

Enter the key element: 4

Element found at position 4

(6) Write a program that uses a function to implement Bubble sort.

Bubble Sort is the simplest sorting algorithm that works by repeatedly

swapping the adjacent elements if they are in the wrong order.

In this algorithm,

 traverse from left and compare adjacent elements and the higher one is

placed at right side.

 In this way, the largest element is moved to the rightmost end at first.

 This process is then continued to find the second largest and place it

and so on until the data is sorted.

#include<stdio.h>

void bubblesort(int a[], int n)

int i, j, t;

for(i=1; i<n; i++) /* Number of Passes*/

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

if(a[j] > a[j+1])

t = a[j];

a[j] = a[j+1];

a[j+1] = t;

}
 }

int main()

int i, n, a[30];

printf(“Enter the range:”);

scanf(“%d”, &n);

printf(“Enter %d elements”, n);

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

scanf(“%d”, &a[i]);

bubblesort(a, n);

printf(“Elements after sorting:”);

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

scanf(“%d ”, a[i]);

return 0;

OUTPUT:

Enter the range: 5

Enter 5 elements: 3 1 5 4 2

Elements after sorting: 1 2 3 4 5

(7) Write a program that uses a function to implement selection sort.

Selection sort is a simple and efficient sorting algorithm that works by

repeatedly selecting the smallest (or largest) element from the unsorted

portion of the list and moving it to the sorted portion of the list.
The algorithm repeatedly selects the smallest (or largest) element from

the unsorted portion of the list and swaps it with the first element of

the unsorted part. This process is repeated for the remaining unsorted

portion until the entire list is sorted.

#include<stdio.h>
void selectionsort(int a[], int n)
{
int i, j, t, min;

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

{
min = i-1;
for(j=i; j<n; j++)
{
if(a[j] < a[min])
min = j;
}
t = a[i-1];
a[i-1] = a[min];
a[min] = t;
}
}
int main()
{
int i, n, a[30];
printf(“Enter the range:”);
scanf(“%d”, &n);
printf(“Enter %d elements”, n);
for(i=0; i<n; i++)
scanf(“%d”, &a[i]);
selectionsort(a, n);
printf(“Elements after sorting:”);
for(i=0; i<n; i++)
scanf(“%d ”, a[i]);
return 0;
}

OUTPUT:
 Enter the range: 5
Enter 5 elements: 3 1 5 4 2
Elements after sorting: 1 2 3 4 5

(8) Write a program that uses a function to implement Insertion sort

Insertion sort is a simple sorting algorithm that works similar to the

way you sort playing cards in your hands. The array is virtually split

into a sorted and an unsorted part. Values from the unsorted part are

picked and placed at the correct position in the sorted part.

To sort an array of size N in ascending order iterate over the array and

compare the current element (key) to its predecessor, if the key element

is smaller than its predecessor, compare it to the elements before. Move

the greater elements one position up to make space for the swapped

element.

#include<stdio.h>

void insertionsort()

int i, j;

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

for(j=i; (j>0 && a[j]>a[j-1]); j--)

if(a[j] < a[j-1])

t = a[j];

a[j] = a[j-1];

a[j-1] = t;
 }

int main()

int i, n, a[30];

printf(“Enter the range:”);

scanf(“%d”, &n);

printf(“Enter %d elements”, n);

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

scanf(“%d”, &a[i]);

insertionsort(a, n);

printf(“Elements after sorting:”);

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

scanf(“%d ”, a[i]);

return 0;

OUTPUT:

Enter the range: 5

Enter 5 elements: 3 1 5 4 2

Elements after sorting: 1 2 3 4 5

(9) Write a program that uses a function to implement Quick sort.

QuickSort is a sorting algorithm based on the Divide and Conquer

algorithm that picks an element as a pivot and partitions the given

array around the picked pivot by placing the pivot in its correct position

in the sorted array.

The key process in quickSort is a partition(). The target of partitions

is to place the pivot (any element can be chosen to be a pivot) at its

correct position in the sorted array and put all smaller elements to the

left of the pivot, and all greater elements to the right of the pivot.

Partition is done recursively on each side of the pivot after the pivot is

placed in its correct position and this finally sorts the array.

#include<stdio.h>

void quicksort (int a[], int first, int last)

int i, j, t, pivot;

if(first < last)

pivot = first;

i = first+1;

j = last;

while(i<=j)

{
 while(a[i] <= a[pivot] && i<=last))

i++;

while(a[j] >= a[pivot] && j>=1)

j--;

if(i<j)

t = a[i];

a[i] = a[j];

a[j] = t;

t = a[pivot];

a[pivot] = a[j];

a[j] = t;

quicksort(a, first, j-1);

quicksort(a, j+1, last);

int main()

{
int i, n, a[50];

printf(“Enter the range: “);

scanf(“%d”, &n);

printf(“Enter %d elements: “, n);

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

scanf(“%d”, &a[i]);

quicksort(a, 0, n-1);

printf(“Elements after sorting: “);

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

printf(“%d “, a[i]);

return 0;

OUTPUT:

Enter the range: 5

Enter 5 elements: 3 1 5 4 2

Elements after sorting: 1 2 3 4 5