C++ Recursion, Inductive Proof. Hi there, below are my recursive functions and I
ID: 3863984 • Letter: C
Question
C++ Recursion, Inductive Proof.
Hi there, below are my recursive functions and I have to prove the functions work as they are supposed to by using inductive proof.
Can anyone write the inductive proof for all my functions including bases case and inductive case?
I commented out on top of each function to let you know what the function is doing.
Thank you in advance!
// Implement the function that computes the sum of all even numbers less than n
int sum_evens(unsigned int n){
if(n == 0)
return 0;
if(n % 2 == 0)
return n + sum_evens(n - 2);
else
return sum_evens(n - 1);
}
// Recursively implement multiplication of two unsigned ints, a and b, using only addition. If you use *, you get no credit. Assume that a >= 0.
int multiply(unsigned int a, unsigned int b){
if(b == 0)
return 0;
if(b == 1)
return a;
else
return a + multiply(a, b - 1);
}
// Implement a function to find the smallest element in an array of int:
int smallest(int* arr, int length){
if(length == 1)
return arr[0];
length--;
return smallest(arr + (arr[0] > arr[length]) , length);
}
// Implement a function that tests whether a string is a palindrome (reads the same backwards and forwards).
bool is_palindrome(string s){
if(s.length() < 2)
return true;
if(s[0] != s[s.length() - 1])
return false;
string substring = s.substr(1, s.length -1);
if(!is_palindrome(substring))
return false;
else
return true;
}
// Implement a function that determines whether a given int is an element of an array of int:
bool is_element_of(int i, int* array, int length){
if(length < 0)
return false;
if(array[length] == i)
return true;
else
return is_element_of(i, array, length - 1);
}
// Using your function above, implement a function which determines whether one array is a “subset” of another
// (that is, whether every element in array a is also an element of array b):
bool is_subset(int* a, int length_a, int* b, int length_b){
if(!is_element_of(b[length_b], a, length_a))
return fasle;
else
is_subset(a, length_a, b, length_b -1);
return true;
}
Explanation / Answer
Proof by induction: Sum of evens
Sum of all even numbers means identify the if the number is divisible by 2 and keep on adding them till the count goes down to 0
e.g., for 5 even numbers are (4,2)
for 10 (10,8,6,4,2)
Base case: For an unsigned number k = 1, execute the recursive function.
Iteration 1: 1%2 = 0, k = 1-1=0
Iteration 2: As n == 0, return 0
Hence, sum = 0
Algorithm holds true.
Inductive case: Let k = n, where n is an odd number
S = (n-1) + (n-3) + (n-5)…+0
Execute the algorithm:
Iteration 1:
If n is an odd number, first even number is determined by subtracting 1 from the number.
i.e., n-1 is returned.
Iteration 2:
As we know, if n is an odd number, n-1 will be an even number, so it goes in condition one.
It returns (n-1) + sum of (n-1-2) = (n-1) + Sum(n-3)
Iteration 3: If we subtract an odd number from an odd number, result is even, so n-3 is an even number and hence it also goes in first condition.
Sum = (n-1) + (n-3) + Sum(n-5)
And it goes on till n = 0
Thus, sum = (n-1) + (n-3) + (n-5)…+0
Sum = S
Hence algorithm holds true.
===================================================================
Proof by induction: Multiplication of 2 unsigned integers
Multiplication of 2 numbers(m*n) can be stated as addition of number m, n times
Base case: For an unsigned number b = 1, execute the recursive function.
Iteration 1: as b == 1, return a
As any number multiplied by 1 remains same.
Hence, product = a
Algorithm holds true.
Inductive case: Let b = n,
P =m*n= (m) + (m) + (m)…+m (n times)
Execute the algorithm:
Iteration 1:
Goes in else case, and returns m+multiply(m,n-1)
Iteration 2:
If n-1 is greater than 1, then it goes in else case and returns m+ multiply(n-2)
Iteration 3: This repeats till n goes down to 1.
Product = m + m + …….m (n times)
Product = P
Hence algorithm holds true.
===================================================================
Proof by induction: Smallest element in an array of int
Base case: For an array of length l = 1, execute the recursive function.
Iteration 1: if length == 1, then the only element in the array becomes the smallest number.
Hence, smallest = a
Algorithm holds true.
Inductive case: Let l = n, where n>1
Execute the algorithm:
Iteration 1: length = n-1
Compare the last element with first element of array.
If First element is greater than last, 1 is added to first element of array, else 0 is added to first element
And recursively calls function for array of l = n-1,
Goes in else case, and returns m+multiply(m,n-1)
Iteration 2:
If n-1 is greater than 1, then it goes in else case and returns m+ multiply(n-2)
Algorithm fails.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.