Recursion Exercise

Program 1. Given two non negative integers, m and n, your recursive function should compute the highest common factor (HCF), also known as greatest common divisor (GCD) using the following algorithm:

• If m or n is zero then, respectively, n or m is the GCD.
• If m is equal to n then m is the GCD.
• IF m > n then the GCD is the GCD of (m-n) and n.
• If n > m then the GCD is the GCD of (n-m) and n.

Program 2. Given that array, say A, of length n contains non-negative integers and given another non-negative integer, say k, do a linear search of A for k using recursion: If n is equal to 1 then if A[0] is equal to k then the value returned is true otherwise he value returned is false. If n > 1 then if A[n-1] == k then the value returned is true else search the array through its n-1 cells.

Program 3. Modify the program that produces permutations of n things taken n at a time to produce permutations of n things taken r at a time. I have given you the program that needs to be modified