Question

3. 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)

1. Set up and solve a recurrence relation for the number of times the algo- rithm’s basic operation is executed.

2. How does this algorithm compare with the straightforward nonrecursive algorithm for computing this sum?

Answer 1

Recurrence relation is:

Now for n=5

S(5)= S(4)+ 5/fact(5)

S(5)= S(4)+ 5/factorial(5);
= S(3)+ 4/factorial(4)+ 5/factorial(5);
= S(2)+ 3/factorial(3)+ 4/factorial(4)+ 5/factorial(5);
= S(1)+ 2/factorial(2)+ 3/factorial(3)+ 4/factorial(4)+ 5/factorial(5);
= 1+ 1 + 3/6 + 4/24+ 5/120 ;
= 2.7083

To calculate and compare running time, see the code

#include <bits/stdc++.h>
using namespace std;
#define ll double

ll factorial(ll n){
    ll fact=1;
    while(n>0){
        fact=fact*n;
        n--;
    }
    return fact;
}

ll recursiveSum(ll n){
    if(n==1)
    return 1;
    
    return recursiveSum(n-1)+ n/factorial(n);
}

ll iterativeSum(ll n){
    ll sum=0;
    
    for(ll i=1;i<=n;i++){
        sum+= i/factorial(i);
    }
    return sum;
}

int main()
{


ll n=30;

clock_t start,end;
start=clock();
cout<<"Sum is: "<<fixed<<setprecision(4)<<recursiveSum(n)<<" ";
end=clock();
 double time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    cout << "Time taken by recursive program is : " << fixed  
         << time_taken << setprecision(5); 
    cout << " sec " << endl; 

start=clock();    
cout<<"Sum is: "<<fixed<<setprecision(4)<<iterativeSum(n)<<" ";
end=clock();
  time_taken = double(end - start) / double(CLOCKS_PER_SEC); 
    cout << "Time taken by iterative program is : " << fixed  
         << time_taken << setprecision(5); 
    cout << " sec " << endl; 

        return 0;
}

For n=30

Recursive appraoch= 0.0001s

Iterative Approach= 0.0000s