1. Euclidean Algorithm
Euclidean Algorithm is an algorithm to calculate greatest common divisor (gcd) of two integers. Suppose that we want to calculate gcd of two integers x and y where x>y.
gcd(x,y)=gcd(y,x%y) where x%y is the remainder Here is an example:
gcd(219, 93) = gcd(93,33) since 219%93=33
= gcd(33,27) since 93%33 = 27
= gcd(27,6) since 33%27 = 6
= gcd(6,3) since 27%6 =3
= gcd(3,0) since 6%3 =0 STOP
You should stop if the remainder is 0. gcd is the last nonzero remainder.
Write a recursive method which takes as parameter two integers and returns their gcd.
2. Population growth
Assume that a city with currently 1 million people has a population growth rate of 1% per year, and it also receives 1 thousand immigrants per year. Find its population in 10 years from now by writing a recursive method called population which takes the year n as its parameter and returns the population after n years.
3. Staircase – Tribonacci Numbers
Suppose you want to walk up a staircase, and you can take 1, 2 or 3 steps at a time. How many ways are there to walk the 6 steps?
For instance, you can take 1-1-1-1-1-1, 3-3, 3-1-1-1.
Let Sn denote the number of ways to walk n steps. Write a recursive relation by thinking of the last step you are going to take. (There are 3 possibilities.)
Using the recurrence relation you have found write a recursive algorithm to solve the problem.
4. Write a function using recursion to check if a number n is prime (you have to check whether n is divisible by any number below n).
5. Write a function using recursion that takes in a string and returns a reversed copy of the string. The only string operation you are allowed to use is string concatenation
6. Write a recursive function that converts a number from the 10th number system to binary. The function returns the result as a number. For instance, 13 will be converted to 1101.
