Question

Write recursive algorithms for the following actions and for some prove the correctness of the algorithm.

a) Reverse a string s.
b) Compute exponent: r^nProve that your algorithm is correctly calculating exponent.
c) Compute factorial: n ! Prove that your algorithm is correctly calculating factorial.
d) Compute sum: ∑ⁿₖ_=₁ k Prove that your algorithm is correctly calculating sum.

Answer 1

Recursive algorithms have been defined for reversing a string, computing exponent, factorial, and sum of a series. Mathematical induction can be used to prove the correctness of algorithms for exponentiation and factorial.

Step-by-step explanation:

To reverse a string s, we can define a recursive function that takes the string as input and concatenates the last character of the string with the reverse of the substring excluding the last character. This continues until the substring is empty.

For computing an exponent r^n, the recursive algorithm will multiply the base r by the result of the same function with the exponent decreased by one, that is, r × r^(n-1), until n equals zero, in which case it will return 1 as anything raised to the power 0 is 1. To prove correctness, we rely on the definition of exponentiation and mathematical induction.

Computing the factorial of a number n! is done by multiplying the number n with the result of factorial of n-1. The base case is n = 1 or n = 0, both yielding a result of 1. We can prove this correct using mathematical induction.

For computing the sum of a series ∑ⁿ_₁ k, we recursively add k to the sum of numbers from 1 to k-1 until k is 1. The base case is k = 1, which returns 1. This follows directly from the definition of summation.