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 algorithms

basic operation is executed.

b. How does this algorithm compare with the straightforward nonrecursive

algorithm for computing this sum?