Write iterative and recursive versions of functions that compute the sum of comp

Question

Write iterative and recursive versions of functions that compute the sum of components of an array. Fill the array with random numbers from 0 to 1 using the function double(rand( ))/double(RAND_MAX). Develop a main program for measuring differences in execution time of iterative and recursive version of the program. For time measurements use the following function:

double sec(void){return double(clock( ))/CLOCKS_PER_SEC;}.

In this measurement (and in all other time measurement problems) you must get reliable time measurements using the clock( ) function that has typical resolution of 10 ms. Consequently, comfortable measurement should take 3 seconds or more, and that can be achieved by repeating the measured code segment inside a for loop.

Explanation / Answer

#include <iostream>

#include <stdlib.h>

#include <time.h>

using namespace std;

double* fill_array(int size){

double* arr = (double*) malloc(size);

srand (time(NULL));

for(int i=0;i<size;i++){

arr[i] = (double) rand()/(double) RAND_MAX;

}

return arr;

}

double sec(void){return double(clock( ))/CLOCKS_PER_SEC;}

double time_iterative(double* arr, int size){

double sum=0.0;

for(int i=0;i<size;i++){

sum+=arr[i];

}

return sum;

}

double time_recursive(double* arr, int size){

if(size==0) return 0.0;

else{

double sum = arr[size-1] + time_recursive(arr,size-1);

return sum;

}

}

int main(){

int size = 10000;

double* arr = fill_array(size); //fill array of size 10000 with random nos.

double t0 = sec(); //time before start of measurement

for(int i=0;i<10000;i++)

time_iterative(arr, size); //iterative function called over 10000 times

double t1 = sec(); //time after end of measurement

//similar to iterative is recursive

double t2 = sec();

for(int i=0;i<10000;i++)

time_recursive(arr, size);

double t3 = sec();

double ti = t1-t0;

double tr = t3-t2;

double diff = tr-ti; // take the difference (recursive - iterative)

cout<<diff<<endl;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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