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