Scribd
Upload
3 views

Solution Exercise Recursion

The document contains a series of programming exercises focused on recursion and iteration, including tasks for calculating factorials, string lengths, sums of squares, and binary conversions. It also includes functions for searching elements in arrays, checking for palindromes, calculating the greatest common divisor, evaluating polynomials, and determining combinations using Pascal's triangle. Each exercise is accompanied by example code implementations in C++.

Uploaded by

hadytarabay12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views

Solution Exercise Recursion

The document contains a series of programming exercises focused on recursion and iteration, including tasks for calculating factorials, string lengths, sums of squares, and binary conversions. It also includes functions for searching elements in arrays, checking for palindromes, calculating the greatest common divisor, evaluating polynomials, and determining combinations using Pascal's triangle. Each exercise is accompanied by example code implementations in C++.

Uploaded by

hadytarabay12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

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);
}

You might also like