/*
Theory:Recursion is a programming technique where a function calls itself to solve a problem. It breaks down complex problems into simpler, smaller instances of the same problem. Each recursive call progresses towards a base case, which stops the recursion. It’s commonly used in tasks like sorting, searching, and traversing data structures. Properly defined base cases are essential to prevent infinite loops.
*/
//Write a program to compute an mod m 
#include <conio.h>
#include<stdio.h> 
using namespace std;  
int exponentMod(int A, int B, int C) 
{ 
    if (A == 0) 
        return 0; 
    if (B == 0) 
        return 1;  
    long y; 
    if (B % 2 == 0) { 
        y = exponentMod(A, B / 2, C); 
        y = (y * y) % C; 
    } 
      else 
	  { 
        y = A % C; 
        y = (y * exponentMod(A, B - 1, C) % C) % C; 
    } 
  
    return (int)((y + C) % C); 
}
int main() 
{ 
    int b = 12, n = 2, m = 5; 
    printf(" %d^%d mod %d = %d",b,n,m,exponentMod(b, n, m)); 
    return 0; 
} 

// Program 2
//binary search recursion
#include<stdio.h>
#include<conio.h>
int binSearch(int arr[],int key,int l,int r);
int main()
{
	int arr[] = {11,12,13,14,15,16,17,18,19,20};	
	int key=19;
	int pos = binSearch(arr,key,0,10);
	if(pos<0)
	printf("Key item not found");
	else
	printf("Key item found at location %d\n",pos);
	getch();
	return 0;
}
int binSearch(int arr[],int key, int l,int r)
{
    if(l<r)
    {    
 	    int m = (l+r)/2;
 	    if(arr[m]==key)
 	    return m+1;
 	    else if(key<arr [m])
 	    return binSearch(arr,key,l,m-1);
 	    else
 	    return binSearch(arr,key,m+1,r);
   }   	
}
// Get output pdf at: https://docs.sujan1919.com.np/uploads/ds-lab-13-output.pdf