Academia International College

(Affiliated to Tribhuvan University)

Gwarko, Ring Road, Lalitpur -7, Nepal

Lab Report on
Recursive algorithm

Lab No. 6
Subject: Discrete Structure

Submitted By Submitted To
Name: Bipin Maharjan Ashish Shrestha
Semester :2nd
Roll no :11
Contents
Introduction ................................................................................................................................. 1
Advantages .................................................................................................................................. 1
Disadvantages ............................................................................................................................. 1
1. Exponent calculation ............................................................................................................ 1
2. Modular exponent ................................................................................................................ 1
3. Linear search ........................................................................................................................ 2
Code ............................................................................................................................................ 2
1. Program for exponent calculation ........................................................................................ 2
2. Program to calculate modular exponent .............................................................................. 3
3. Program to calculate linear search ....................................................................................... 4
Output ......................................................................................................................................... 6
1. Output of exponent calculation ............................................................................................ 6
2. Output for modular exponent ............................................................................................... 6
3. Output for linear search ....................................................................................................... 7
References ................................................................................................................................... 8
Introduction
A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values,
and which obtains the result for the current input by applying simple operations to the returned
value for the smaller (or simpler) input. More generally if a problem can be solved utilizing
solutions to smaller versions of the same problem, and the smaller versions reduce to easily
solvable cases, then one can use a recursive algorithm to solve that problem. For example, the
elements of a recursively defined set, or the value of a recursively defined function can be
obtained by a recursive algorithm.

If a set or a function is defined recursively, then a recursive algorithm to compute its members or
values mirrors the definition. Initial steps of the recursive algorithm correspond to the basis
clause of the recursive definition and they identify the basis elements. They are then followed by
steps corresponding to the inductive clause, which reduce the computation for an element of one
generation to that of elements of the immediately preceding generation.

In general, recursive computer programs require more memory and computation compared with
iterative algorithms, but they are simpler and for many cases a natural way of thinking about the
problem. (htt1)

Advantages
 Simplicity of code
 Easy to understand

Disadvantages
 Memory
 Speed
 Possibly redundant work

1. Exponent calculation
The power of a number can be calculated as x^y where x is the number and y is its power.

2. Modular exponent
Modular Exponentiation means computing 𝑎 modulo some other number n. We tend to write
this as 𝑎 𝑚𝑜𝑑 𝑛. Modular exponentiation is easy (Habeeb, 2013).

1
 3. Linear search
Linear search is a very simple search algorithm. In this type of search, a sequential search is made
over all items one by one. Every item is checked and if a match is found then that particular item
is returned, otherwise the search continues till the end of the data collection (tutorialspoint, n.d.).

Code
1. Program for exponent calculation
#include<stdio.h>

int power(int n1, int n2);

int main()

{ int base,a ,result;

printf("enter base number");

scanf("%d",&base);

printf("enter power number(Positive integer):");

scanf("%d",&a);

result=power(base,a);

printf("%d^%d=%d",base,a,result);

return 0;

int power(int base,int a)

{ if(a!=0)

return (base*power(base,a-1));

else

return 1;

2
}

2. Program to calculate modular exponent

#include<conio.h>

using namespace std;

int modular(int,int,int);

int main()

int x,n,M,result;

cout<<"enter a base number"<<endl;

cin>>x;

cout<<"enter a power number"<<endl;

cin>>n;

cout<<"enter a number"<<endl;

cin>>M;

result=modular(x,n,M);

cout<<x<<"^"<<n<<"%"<<M<<"="<<result<<endl;

return 0;

int modular(int x,int n, int M)

int y;

if(n == 0)

3
 return 1;

else if(n%2 ==0)

y=modular(x,n/2,M);

return(y*y)%M;

else

return((x%M)*modular(x,n-1,M))%M;

3. Program to calculate linear search

using namespace std;

int search(int arr[], int n, int x)

int i;

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

if (arr[i] == x)

return i;

return -1;

4
}

// Driver code

int main()

int arr[] = { 1,2, 3, 4, 5,6 };

int n = sizeof(arr) / sizeof(arr[0]);

int x = 2; //x=0

// Function call

int index = search(arr,n,x);

if(index == -1)

cout<<"element is not present in the array";

else

cout<<"element found at position"<<index;

return 0;

/* int result = search(arr, n, x);

(result == -1)

cout << "Element is not present in array"

cout << "Element is present at index " << result;

return 0; */

5
Output
1. Output of exponent calculation

2. Output for modular exponent

6
3. Output for linear search

7
References
(n.d.). Retrieved from [Link]
Habeeb, A. (2013, 04 28). slideshare. Retrieved from [Link]:
[Link]
tutorialspoint. (n.d.). Retrieved from tutorialspoint:
[Link]