Exercises
Exercise 1
• Find the number of calls done for the factorial function with n=10.
Exercise 2
• Write an iterative and recursive function for calculating the length of a string of
characters.
Exercise 3
• Write a recursive function that returns the sum of squares for the first n
elements of an array with positive integers.
Exercise 4
• Write an iterative function that converts from decimal to binary.
Exercise 5
• Write a recursive function that finds the smallest element in an array
1
Exercises
Exercise 6
• Write an iterative and recursive function for searching the element
index of an element in an array of names sorted in alphabetic order
Exercise 7
• Write a recursive boolean function that determines if a string in
palindrom or not. E.g., the word LAYAL is palindrom
Exercise 8
• Write a recursive function that calculates the pgcd of 2 numbers
using the Euclidian method
• pgcd(a,b)=a if a=b
• pgcd(a,b)= pgcd(a-b,b) if a>b
• pgcd(a,b)= pgcd(a,b-a) if b>a 2
Exercises
Exercise 9
• Write a recursive function that evaluates a polynom having the
form a0+a1x+a2x2+…+anxn, where x and n are passed as integer
arguments, and the n+1 coefficients ai are passed to the function as
an array
Exercise 10
• Write a recursive function that determines the combination number
of k objects between n, using the Pascal triangle
• C(n,k)=1 if k=0
• C(n,k)=1 if k=n
• C(n,k)= C(n-1,k-1)+ C(n-1,k) if 0<k<n
• C(n,k)=0 if k<0 3
//Recursion ex1 : number of calls for factorial of 10
int factorial (int n)
{
if (n<=1)
return 1;
return n * factorial (n-1);
}
factorial(10): n=10, return 10 * factorial(9)
factorial(9): n = 9, return 9 * factorial(8)
factorial(8): n = 8, return 8 * factorial(7)
factorial(7): n = 7, return 7 * factorial(6)
factorial(6): n = 6, return 6 * factorial(5)
factorial(5): n = 5, return 5 * factorial(4)
factorial(4): n = 4, return 4 * factorial(3)
factorial(3): n = 3, return 3 * factorial(2)
factorial(2): n = 2, return 2 * factorial(1)
factorial(1): n = 1, return 1
➔ 10 calls
//Recursion ex2 : length of a string
int length(char *str)
{
if(*str=='\0')
return 0;
return 1+length (str+1);
}
//Recursion ex3 : sum of squares for the first n elements of an
//array with positive integers
int sumsquare (int *A, int n)
{
if(n==0)
return 0;
return A[n-1]*A[n-1] + sumsquare(A, n-1);
}
//ex4: iterative function that converts from decimal to binary
long dectobin(int n)
{
long bin = 0, i=1;
while(n!=0)
{
bin = bin + n%2 * i;
i=i*10;
n=n/2;
//ex5: find the smallest element in an array
}
return bin; int smallest (int *A, int n)
} {
if(n<=1)
return A[0];
int min = smallest (A, n-1);
if(A[n-1] < min)
return A[n-1];
else
return min;
}
//ex6: iterative function for searching the element index
We will consider a template array to accept all kinds of type
template <typename T>
// Iterative binary search function to find the index of a target in a sorted array
int binarySearchIterative(T arr[], int n, T target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the target is at the middle
if (arr[mid] == target)
return mid;
// If target is greater, ignore the left half
if (arr[mid] < target)
low = mid + 1;
// If target is smaller, ignore the right half
else
high = mid - 1;
}
// If not found, return -1
return -1;
}
//ex6: recursive function for searching the element index
We will consider a template array to accept all kinds of type
template <typename T>
// Recursive binary search function to find the index of a target in a sorted array
int binarySearchRecursive(T arr[], int low, int high, T target) {
if (low <= high) {
int mid = low + (high - low) / 2;
// Check if the target is at the middle
if (arr[mid] == target)
return mid;
// If target is greater, search the right half
if (arr[mid] < target)
return binarySearchRecursive(arr, mid + 1, high, target);
// If target is smaller, search the left half
return binarySearchRecursive(arr, low, mid - 1, target);
}
// If not found, return -1
return -1;
}
//ex6: Main
int main() {
int A[10] = {9,8,7,6,5,4,3,2,1,0};
int n = 10;
int target = 4;
// Iterative search
int indexIterative = binarySearchIterative(A, n, target);
if (indexIterative != -1)
cout << "Found " << target << " at index (iterative): " << indexIterative << endl;
else
cout << target << " not found (iterative)." << endl;
// Recursive search
int indexRecursive = binarySearchRecursive(A, 0, n - 1, target);
if (indexRecursive != -1)
cout << "Found " << target << " at index (recursive): " << indexRecursive << endl;
else
cout << target << " not found (recursive)." << endl;
return 0;
}
//ex7: recursive boolean function that determines
//if a string in palindrom or not
bool isPalindrom (char * str, int s, int e)
{
if (s>=e)
return true;
if (str[s]!=str[e])
return false;
return isPalindrom (str, s+1, e-1);
//ex8: pgcd of 2 numbers
int pgcd (int a, int b)
{
if(a==b)
return a;
else if(a>b)
return pgcd (a-b, b);
else
return pgcd(a, b-a);
}
//ex9: function that evaluates a polynom having the form a0x^0+a1x^1+a2x^2+…+anx^n,
//where x and n are passed as integer arguments,
//and the n+1 coefficients ai are passed to the function as an array
int polynome (int x, int n, int *A, int i)
{
if(i==n)
return A[0];
return A[i]*pow(x,n) + polynome (x, n, A, i+1);
}
int main()
{
int A[4] = {1, 2, 3, 4};
int x = 2;
int n = 3;
cout<<polynome (x, n, A, 0);
return 0;
}
//ex9: recursive function that determines the combination number of k objects between n, using the Pascal triangle
int combination(int n, int k)
{
// Base cases
if (k == 0 || k == n) {
return 1; // C(n, 0) = 1 and C(n, n) = 1
}
if (k < 0) {
return 0; // C(n, k) = 0 if k < 0
}
// C(n, k) = C(n-1, k-1) + C(n-1, k)
return combination(n - 1, k - 1) + combination(n - 1, k);
}
