DS chapter3.ppt...................................

ppt

1. Recursion
•A recursive function is a function that is defined in terms
of itself.
•An algorithm is said to be recursive if the same algorithm
is invoked in the body.
•An algorithm that calls itself is direct recursive.
•Algorithm A is said to be indirect recursive if it calls
another algorithm which in turn calls A.
•In recursive the calling function and called function are
same.

2. Iterative version to compute factorial of n:
 The factorial of a number n is the product of integer
values from 1 to n. The iterative definition to compute n! is
shown below,
Fact(n) = 1 if n = 0
n * (n-1) * (n-2)*……*3*2*1. if n>0.
Based on the above definition the algorithm can be
designed as follows,

3. Initial: fact = 1
Step1 : fact = fact *1
Step2:fact = fact *2
Step3 : fact = fact *3
.
.
.
Step n : fact = fact *n
From above steps we can write,
fact = fact * i where, i = 1,2,…….n.

4. Algorithm factorial (int n)
{
int fact, i;
fact:= 1;
for (i=1; i<=n; i++)
{
fact = fact * i;
}
return fact;
}

5. Properties of recursive definition :
The recursive function must satisfy following
properties,
The function must have stopping condition. i.e., it
should not continue to call indefinitely.
Each time the function calls itself, it must be in the
recursive form, i.e., it must be nearer to a solution.

6. Advantage of recursion :
1.Recursion reduces the complexity of the problem.
2.Recursion allows users to write much simpler programs.
3.Program implemented by recursion will be smaller in length.
4.Recursion programs can have any no of nesting levels.
5.Recursion is a top-down programming tool, where the given
problem is divided into smaller modules, each module are then
individually attached.

7. How it works :
The recursive function calls are initially pushed
on to the stack until the condition is encountered.
After the termination condition is encountered,
the recursive functions that were pushed onto the stack are
popped from the stack one-by-one.
So, stack data structure plays the major role in
executing recursive functions.

8. Recursive version to compute factorial of n:
The recursive definition to compute n! is show below,
fact (n) = 1 if n=0 (Base case)
n*fact(n-1) if n>0 (General case)
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
1! = 1 * 0! = 1
2! = 2*1!=2
3! = 3 * 2!=6
4!= 4* 3!= 24
5!= 5* 4!= 120

9. Algorithm fact(int n)
{
if (n==0)
return 1;
return n * fact (n-1);
}

10. Fibonacci series :
The Fibonacci numbers are a series of
numbers such that each number is the sum of the
previous two numbers except the first and the second
number.
Ex : 0,1,1,2,3,5,8,13,21,34,………………..
To write a recursive definition we should know the
base case and general case.
Base case : Fib (0) = 0 and Fib (1) = 1
General case : Fib (n) = Fib (n-1) + Fib (n-2)

11. C program to display n Fibonacci numbers :
# include < stdio.h >

int fib( int n )
{
if ( n==0 ) return 0;
if ( n==1 ) return 1;
return fib( n-1 ) + fib ( n-2 );
}

12. void main()
{
int i, n;
printf(“Enter the value of n”);
scanf(“%d”, &n);
printf(“Fibonacci numbers are”);
for ( i=0; i<n,i++ )
{
printf(“fib(%d) = %d\n”,i,fib(i));
}
}

13. Tower of Hanoi :
Here there are 3 needles A, B, & C & ‘n’ discs, of
different diameters in the needle A, & are placed one above the
other such that always a smaller disc is placed above the larger disc.
The two needles B & C are empty.
All the discs from needle A are to be transferred to
needle C using needle B as temporary storage.
The following rules to be followed while transferring the
discs,
only one disc is moved at a time from one needle to another
needle.
Smaller disc is on top of the larger disc at any time.
Only one needle can be used to for storing intermediate disks.

14. Solution:
If n = 2, there will be 2
n
– 1 moves her it is 3.
A -> B , A –> C, B ->C.
i.e., A -> B tower(n-1, source, dest, temp);
A -> C printf(“Move the disc from %c to %c”,
source, dest);
B -> C tower(n-1, temp, source, dest);
i.e., The base condition is, if n == 1 in source then directly
transfer from source to destination

15. // C function for tower of Hanoi
 #include < stdio.h >
int count = 0;
 void tower(int n, int source, int temp, int dest)
{
if( n == 1)
{
printf(“\n move the disc from %c to %c “, source, dest);
count++;
return;
}
tower (n-1, source, dest, temp);
printf(“\n Move the disk from %c to %c “, source, dest);
tower(n-1, temp, source, dest);
}

16. void main()
{
int n;
printf(“Enter no. of discs”);
scanf(“%d”, &n);
tower(n, ‘A’, ‘B’, ‘C’);
printf(“The total no. of moves = %d”, count);
}

17. Tracing:If n = 3i.e., No. of moves = 2
n
– 1 = 7
T(1, A, B, C) A -> C
T(2, A, C, B) A -> B A -> B
T(1, C, A, B) C -> B
Tower(3, A, B, C) A -> C A -> C
T(1, B, C, A) B -> A
T(2, B, A, C) B -> C B -> C
T(1, A, B, C) A -> C

18. #include <stdio.h>
#include <conio.h>
void tower(int n,char src,char tmp,char dest)
{
if (n!=0)
{
tower (n-1,src,dest,tmp);
printf ("\nMove %d disc from %c to %c",n,src,dest);
tower(n-1,tmp,src,dest);
}
}

19. int sum(int a[], int n)
{
if(n==0)
return (a[0]);
else
return (a[n]+sum(a,n-1));
}
int gcd (int m, int n)
{
if(n==0)
return(m);
if(n>m)
gcd(n,m);
return(gcd(n,m%n));
}

20. int main()
{
int a,b,d,n,i;
int op, key, ans,lcm, ar[15];
clrscr();
while(1)
{
printf("\n-----MENU-----\n\n");
printf("ENTER THE CHOICE");
printf("\n1. GCD AND LCM");
printf("\n2. TOWER OF HANOI");
printf("\n3. SUM OF N numbers");
printf("\n4. EXIT\n");
printf("ENTER THE CHOICE");
scanf("%d",&op);

21. switch(op)
{
case 1: printf("Enter 2 numbers to find GCD and LCM\n");
scanf("%d%d", &a,&b);
clrscr();
ans=gcd(a,b);
lcm = (a*b)/ans;
printf("GCD is %d\n",ans);
printf("LCM is %d\n",lcm);
break;
case 2: printf("Enter the number of discs\n");
scanf("%d", &d);
tower(d,'A','B','C');
break;

22. case 3: printf("Enter the number of elements\n");
scanf("%d",&n);
if (n<1)
{
printf("\nInvalid Input ! Kindly Reenter\n");
break;
}
printf("Enter the %d Array elements\n", n);
for (i=0;i<n;i++)
scanf("%d",&ar[i]);
ans=sum(ar, n-1);
printf("sum of array is : %d\n", ans);
break;
default: return 0;
}
} getch(); }

23. Searching :
The process of finding a particular item in the large
amount of data is called searching.
Different types of searching techniques are,
1. Linear Search.
2. Binary Search.
Linear Search :
A linear search is a simple searching technique.
In this technique we search for a given key item in the list in
linear order. i.e. one after the other.

24. // C function for linear search.
# include < stdio.h >
# include < process.h >
void main ( )
{
int i , n , key , a[20];
printf ( “ Enter the values of n “ );
scanf ( “ %d”, &n );
printf ( “ enter the values” );
for ( i = 0 ; i < n ; i++ )
scanf ( “%d:, &a[i] );
printf ( “ enter the item to be searched” );
scanf ( “%d”, &key );

25. for ( i=0 ; i<n ; i++ )
{
if ( a[i] == key )
{
printf ( “ Item found” );
exiy (0);
}
}
print ( “ not found “ );
}

26. Binary Search :
It is a simple searching technique which can be
applied if the items to be compared are either in ascending
order or descending order.
Method :
The program can be designed as follows,
If low is considered as the position of the first element
and high as the position of the last element, the position of
the middle element can be obtained using the statement,
mid = ( low + high ) / 2 ;

27. The key to be searched is compared with middle
element. This can be done using the statement,
if ( key == a[mid] )
{
pos = mid;
return;
}
If this condition is false, key may be in
the left part of the array i.e. < mid or in the right part of
the array i.e. > mid.

28. If the key is less than the mid, the table has to
compared from low to mid-1. otherwise the table has to
compared from mid+1 to high.
if ( key < a[mid] )
high = mid - 1;
else
low = mid + 1;

29. #include<stdio.h>
#include<conio.h>
void read(int a[], int *n, int *key)
{
int i;
printf("Enter the number of elements\n");
scanf("%d",n);
printf("Enter the elements\n");
for(i=0;i<*n;i++)
scanf("%d",&a[i]);
printf("Enter the key element to be searched\n");
scanf("%d",key);
}

30. void bsort(int a[], int n)
{
int i, j, temp, flag=1;
for(j=1; j < n & flag == 1; j++)
{
flag=0;
for(i=0; i < n-j; i++)
if(a[i] > a[i+1])
{
temp = a[i]; a[i] = a[i+1]; a[i+1] = temp; flag = 1;
}
} printf("\n Sorted Array is \n");
for(i=0;i<n;i++)
printf("%d ", a[i]);
}

31. int ls(int a[], int low, int high, int key)
{
if(low > high)
return(-1);
if(a[low] == key)
return low;
else
return ls(a, low+1, high, key);
}

32. int bs(int a[], int low, int high, int key)
{
int mid;
if(low > high)
return (-1);
mid = (low+high)/2;

if(key == a[mid])
return(mid);
if(key < a[mid])
return bs(a,low,mid-1, key);
else
return bs(a, mid+1, high, key);
}

33. void main()
{
int a[100],n,key,ch, ans;
clrscr();
while(1)
{
printf("\n Select a search\n");
printf(" 1. LINEAR SEARCH\n");
printf(" 2. BINARY SEARCH\n");
printf(" *. Exit\n");
printf("Enter the choice(1 or 2 or 3)\n");
scanf("%d", &ch);

34. switch(ch)
{
case 1: read(a, &n, &key);
ans = ls(a, 0, n, key);
if(ans == -1)
printf("\n Key not found \n");
else
printf("\n Key found at %d\n",ans);
break;

35. case 2: read(a, &n, &key);
bsort(a, n);
ans = bs(a, 0, n, key);
if(ans == -1)
printf("\n Key not found \n");
else
printf("\n Key found at %d\n",ans);
break;
default: return;
}
}
}