ALL QUESTION ARE COMPULSORY

Q1). Write a function to recusively compute the sum of digits of a positive integer. The function has to be recursive.
	Function Protype : int sum(int n);
	Next write a function that utilizes the above function to repeatedly compute the sum of digits till the sum becomes
	a single-digit number. Output each intermediate sum and final sum. (30 marks)
	
	Example: 
	Input: 1876
	
	Output:
	22 ( 1 + 8 + 7 + 6 ) / you dont have to print what is written in the braces its just to help you understand.
	4  ( 2 + 2)
	
	
Q2). Write a recursive function to compute all permutation of a word of size n. Assume the word will only contain 
	alphabets.
	Output each permutation on a new line. The permutation can be printed in any order. 
	Assume the word will not contain duplicate characters ( 50 marks)
	
	Example :- 
	input
	A B c
	Output
	A B C
	B A C
	B C A
	A C B
	B C A
	C A B
	
	Hint: For permutation of n char, start by choosing 1 of the n chars, and then solve the problem of n-1 char, 
	i.e. permutation of n-1 chars (recursively). Combine the permutations for n-1 chars with the chosen char, 
	we get a subset of the required set of permutations. Follow the process by choosing each one of the remaining chars.

	Example, consider permutation of {'A', 'B', 'C'} i.e. 3 chars. Choose 'A', and permutation of the remaining 
	chars gives {'B C' , 'C B'}. Thus we get 'A B C' and 'A C B'. Now choose 'B' and permute {'A' 'C'} and so on.
	Define a function permutation such that it takes a char array, starting and ending index of the array.
	Use the array to store the intermediate permutation string obtained, and print it when no there are no more 
	chars to permute.


Q3). Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers 
	that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). 
	An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. 
	FindSortedArrayRotation discovers and returns X by examining the array. Make sure your function should not take 
	more than log N steps to find the rotation.
	
	Hint: You can implement this function with the idea of recursive binary search. That is compare the middle element
		with the start of array if smaller than the middle then the rotation lies in the other half of the array. Else
		rotation lies in the first half. Now the problem is reduced by size half, depending upon which half the rotation
		lies you can call the same function with smaller array.
	Example 
	input: 4 5 6 7 8 9 0 1 2 3  ( index value element 0 is from where rotation begins).
	
	Output: index = 6;( 20 marks).