Week 6: Friday
--------------

Q1. (30)

Write a recursive function to compute the gcd (greatest common divisor) of two
positive integers. The gcd of two numbers is the same as the gcd of the
smaller number and the remainder when the larger number is divided by the
smaller number. The base cases are when the two numbers are same (gcd is equal
to them) and when one of them is 1 (gcd is 1).

Write a main function that inputs two positive integers and outputs their gcd.

Q2. (70)

Write a recursive function to compute all the permutations of a set of numbers
of size n. Assume that the numbers are 0 to n-1. Output each permutation on a
line. Separate the numbers from each other by blanks. The permutations can be
printed in any order.

For example, if n = 3, the output should be

0 1 2 
0 2 1 
1 0 2 
1 2 0 
2 0 1 
2 1 0 

Here is one way of writing the program. (You may ignore it and write it in your
own way.)

Initialize an array of size n with the integers 0 to n-1.

Write a for loop that brings all integers to the first position in the array
one at a time by exchanging it with the first element of the array. Print the
first element of the array, and the remaining array from second position
onwards recursively.

Since the array size changes between calls, you can pass a starting index to
the recursive function call that denotes the position from which the array
should be processed. Make sure the base cases (when array size is 1 or 0) are
handled properly.