Problem 1. Given a vector A of integers, write a recursive function that finds the minimum number in A. Your function must have two recursive calls and must return an integer (there is no output).
You need to write the following function with the exact header as shown:
int recMin(const vector<int> &A, int start, int fin);
Example: A = {32, 17, 5, 28, 44, 19, 3, 63}, your function will return 3.
Problem 2. Given a vector A of integers of size n, write a recursive function that calculates the sums of all subarrays A[0…i], 0 ≤ i ≤ n-1. Your function must have one recursive call.
You need to write the following function with the exact header as shown:
void subarraySums(const vector<int> &A, vector<int> &B, int fin);
Example: A = {3, 2, 4, 1, 5}. Initially vector B has the same size as A and initialized to 0. At the end of your function, B = {3, 5, 9, 10, 15}. At entry B[i], the sum A[0]+A[1]+…+A[i] is stored. For example, B[2] = 9 = 3 + 2 + 4.
Problem 3. Given a vector A of integers, write a recursive function that returns true if A is a palindrome; and false, otherwise. Your function must have one recursive call.
You need to write the following function with the exact header as shown:
bool recPal(const vector<int> &A, int first, int last);
Example: A = {3, 2, 1, 2, 3} is a palindrome; A = {3, 2, 2, 3} is also a palindrome; but A = {3, 4, 5, 2, 6, 4, 3} is not.
Problem 4. Given a vector A of distinct integers in increasing order and an integer k. Write a recursive function that returns true if k occurs in A. Your function must have one recursive call.
You need to write the following function with the exact header as shown:
bool recFindSorted(const vector<int> &A, int k, int start, int fin);
Example: A = {12, 15, 17, 21, 34, 59, 67, 82} and k = 67, then your function will return true. If A is the same, but k = 13, then your function will return false.
Problem 5. Given a vector A with distinct integers in increasing order. Write a recursive function that returns an integer index such that index = A[index]. If no such index exists, your function will return -1. Your function must have one recursive call.
You need to write the following function with the exact header as shown:
int findIndex(const vector<int> &A, int start, int fin);
Example: A = {-11, -5, 2, 14, 25, 49, 52}, then your function will return index 2 because 2 = A[2]. If A is A = {-20, 0, 5, 12, 34}, then your function will return -1.
Problem 6. Given a vector A of integers (in any order) and an integer k. Write a recursive function that returns true if k is in A. Your function must have two recursive calls.
You need to write the following function with the exact header as shown:
bool recFind(const vector<int> &A, int k, int start, int fin);
This problem is solved similarly to Problem 1.
Problem 7. Power Set. Given a set of integers (i.e. a vector of distinct integers – sets do not have repeats). Find and print the Power Set of the given set (except for an empty subset). There is one recursive call.
Definition: The Power Set of a given set of integers A is the set of all subsets of A including an empty subset {} and the entire A itself.
Example: A = {2, 5, 4}, PowerSet(A) = { {}, {2}, {5}, {2, 5}, {4}, {2, 4}, {5, 4}, {2, 5, 4} }.
You need to write the following function with the exact header as shown: void powerSet(const vector<int> &A, vector< vector<int> > &P, int last);
Initially, vector P (power set of A) is empty, and by the end of execution, it will contain the power set of A (except for the empty subset).
Problem 8. Print All Permutations. Given a string s of size n. Write a function that prints all permutations of s. Your function must have one recursive call.
Definition: Given a string s of n characters, a permutation of s is a re-ordering of characters in s.
Example: s = “abc”, then all permutations of s are: abc, bac, bca, acb, cab, cba.
You need to write the following function with the exact header as shown:
void findPerms(const string &s, queue<string> &p, int first);
Initially queue p (permutations) is empty, and by the end of execution, it will contain all permutations of s.