Consider the following recursive algorithm for computing the sum of the followin

Question

Consider the following recursive algorithm for computing the sum of the

following series: S(n) = 1/1!+ 2/2!+ . . . + n/n!.

ALGORITHM S(n)

//Input: A positive integer n

// Procedure: fact(n) returns the factorial of the number passed

as parameter

//Output: The sum of the series: S(n) = 1/1!+ 2/2!+ . . . + n/n!

if n = 1 return 1

else return S(n 1) + n/fact(n)

a. Set up and solve a recurrence relation for the number of times the algorithm’s

basic operation is executed.

b. How does this algorithm compare with the straightforward nonrecursive

algorithm for computing this sum?

Explanation / Answer

Since, the fact() function isn't provided, we have to assume that it is a basic operation for this question. Please reconfirm this from your text book or instructor who gave you this question.

a)

The size of the problem decreases by 1 each time.

So, total number times this decrease takes place is n.

And in order to decrease the size of the problem, we have to constant amount of work - in terms of the calculation n/fact(n)

Therefore, total time assymptotic time complexity is O(n).

b) non recursive algorithm will simple replace the recursion with a 'for' loop as follows:

sum = 0

for i = 1 to n:

sum = sum + i/fact(i)

This takes the same time complexity as the recursive function. However, in iterative solution, the stack frames used in recursion are not needed. This decreases the space complexity.

Infact depending on which programming langauge you use, the recursive factorial program may even be optimized by the compiler itself to not need the stack frames.

If you face difficulty in understanding any of this, you can ask me in comments. I will help you further.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.