Program Plan:
- In function “meanIterative()”:
- Compute sum of array elements using a “for” loop.
- Compute mean by dividing sum with number of elements in array.
- In function “varianceIterative()”:
- Compute sum of square of difference between each element with mean.
- Compute variance by dividing it with “n-1”.
- In function “meanRecursive()”:
- If starting index “ii” is same as “n-1”, return element divided by “n”.
- Otherwise, increment the value “ii” by “1” and compute mean all numbers in array by calling function recursively.
- In function “varianceRecursive()”:
- If starting index “ii” is same as “n-1”, return variance of that element.
- Otherwise, increment the value “ii” by “1” and compute variance all numbers in array by calling function recursively.
- In “main()” function:
- Create random input arrays of size “500”, “1000”, “1500” and “2000”.
- For each input array compute standard deviation by using both iterative and recursive functions.
- Compute running time for both and compare each other.
/**********************************************************
* Program to compare running time to compute standard *
* deviation of different sized samples using iterative *
* and recursive functions. *
**********************************************************/
Explanation of Solution
Program:
//Include header files
#include<iostream>
#include<ctime>
using namespace std;
//Iterative function to compute mean of n numbers
double meanIterative(int data[], int n)
{
//Declare variable
double mean;
//Initialize summ as 0
int summ=0;
//Each number from array
for (int i = 0; i < n; i++)
{
//Add number with summ
summ = summ + data[i];
}
//Compute mean of numbers
mean =(double) summ / (double)n;
//Return mean
return mean;
}
//Iterative function to compute variance of n numbers
double varianceIterative(int data[], int n, double mean)
{
//Declare variable
double varianc;
//Initialize summm as 0
double summm=0;
//Each number from array
for (int i = 0; i < n; i++)
{
//Add number with summm
summm = summm + pow((data[i] - mean), 2);
}
//Compute variance
varianc = summm / (float)(n-1);
//Return variance
return varianc;
}
//Recursive function to compute mean of n numbers
double meanRecursive(int data[], int ii,int n)
{
//If starting index ii is equal to n
if (ii == n-1)
//Return mean of that number
return (double)data[ii]/(double)n;
/*Otherwise increment value of ii by 1 and compute mean of numbers by calling function itself recursively*/
return (double)data[ii]/(double)n +meanRecursive(data, ii + 1, n);
}
//Recursive function to compute variance of n numbers
double varianceRecursive(int data[], int ii,int n, double mean)
{
//If starting index ii is equal to n
if (ii == n-1)
//Return variance of that number
return pow((double)data[ii]-mean,2)/(double)(n-1);
/*Otherwise increment value of ii by 1 and compute variance of numbers by calling function itself recursively*/
return pow((double)data[ii]-mean,2)/(double)(n-1) +varianceRecursive(data, ii + 1, n, mean);
}
//Program begins with main() function
int main()
{
//Declare variables
int data_500_S[500],data_1000_S[1000],data_1500_S[1500],data_2000_S[2000];
srand((unsigned)time(0));
//For each index of array of size 500
for(int ii=0;ii<500;ii++)
{
/*Compute random number and store it into array index*/
data_500_S[ii] = rand() % 10000;
}
//For each index of array of size 1000
for(int ii=0;ii<1000;ii++)
{
/*Compute random number and store it into array index*/
data_1000_S[ii] = rand() % 10000;
}
for(int ii=0;ii<1500;ii++)
{
/*Compute random number and store it into array index*/
data_1500_S[ii] = rand() % 10000;
}
for(int ii=0;ii<2000;ii++)
{
/*Compute random number and store it into array index*/
data_2000_S[ii] = rand() % 10000;
}
//Declare variables
double meeanIte, varianceIte,standarddevIte,meeanRec, varianceRecu,standarddevRecu ;
//For array input of size 500
cout<<"For n=500: \n"<<endl;
//Capture current time and store it as initial time
double start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_500_S, 500);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_500_S, 500,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
double stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_500_S, 0,500);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_500_S, 0,500,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//For array input of size 1000
cout<<"\n For n=1000: \n"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_1000_S, 1000);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_1000_S, 1000,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute ruuning time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//Capture current time and store it as initial time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_1000_S, 0,1000);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_1000_S, 0,1000,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli seconds"<<endl;
//For array input of size 500
cout<<"\n For n=1500: \n"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_1500_S, 1500);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_1500_S, 1500,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000 << " Milli seconds"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_1500_S, 0,1500);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_1500_S, 0,1500,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli seconds"<<endl;
//For array input of size 500
cout<<"\n For n=2000: \n"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call iterative function to compute mean of array elements*/
meeanIte=meanIterative(data_2000_S, 2000);
cout<<"Mean using Iterative function is: "<<meeanIte<<endl;
/*Call iterative function to compute variance of array elements*/
varianceIte=varianceIterative(data_2000_S, 2000,meeanIte);
cout<<"Variance using Iterative function is: "<<varianceIte<<endl;
//Compute standard deviation using iterative functions
standarddevIte=sqrt(varianceIte);
cout<<"Standard deviation using Iterative function is: "<<standarddevIte<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for iterative function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) *1000<< " Milli Seconds"<<endl;
//Capture current time and store it as start time
start_s=clock();
/*Call recursive function to find mean of array elements*/
meeanRec=meanRecursive(data_2000_S, 0,2000);
cout<<"\n Mean using Recursive function is: "<<meeanRec<<endl;
/*Call recursive function to find variance of array elements*/
varianceRecu=varianceRecursive(data_2000_S, 0,2000,meeanRec);
cout<<"Variation using Recursive function is: "<<varianceRecu<<endl;
//Compute standard deviation using recursive functions
standarddevRecu=sqrt(varianceRecu);
cout<<"Standard deviation using Recursive function is: "<<standarddevRecu<<endl;
//Capture current time and store it as stop time
stop_s=clock();
//Compute running time in by using start and end time
cout << "Running time for Recursive function: " << (stop_s-start_s)/double(CLOCKS_PER_SEC)*1000<< " Milli Seconds"<<endl;
//Return from program
system("pause");
return 0;
}
Comparison:
Input array size, n | Running time in Milliseconds | |
Iterative Method | Recursive method | |
500 | 17 | 14 |
1000 | 9 | 6 |
1500 | 7 | 7 |
2000 | 7 | 7 |
Conclusion:
- Running time for input array of size “n” equals “500” is larger for iterative method than recursive method.
- For other input arrays the running time for both iterative and recursive are almost similar or sometimes it varies for small values.
Output:
For n=500:
Mean using Iterative function is: 4394.44
Variance using Iterative function is: 8.22268e+006
Standard deviation using Iterative function is: 2867.52
Running time for iterative function: 17 Milli seconds
Mean using Recursive function is: 4394.44
Variation using Recursive function is: 8.22268e+006
Standard deviation using Recursive function is: 2867.52
Running time for Recursive function: 14 Milli seconds
For n=1000:
Mean using Iterative function is: 4908.97
Variance using Iterative function is: 8.77065e+006
Standard deviation using Iterative function is: 2961.53
Running time for iterative function: 9 Milli seconds
Mean using Recursive function is: 4908.97
Variation using Recursive function is: 8.77065e+006
Standard deviation using Recursive function is: 2961.53
Running time for Recursive function: 6 Milli seconds
For n=1500:
Mean using Iterative function is: 4531.62
Variance using Iterative function is: 8.7867e+006
Standard deviation using Iterative function is: 2964.24
Running time for iterative function: 7 Milli seconds
Mean using Recursive function is: 4531.62
Variation using Recursive function is: 8.7867e+006
Standard deviation using Recursive function is: 2964.24
Running time for Recursive function: 7 Milli seconds
For n=2000:
Mean using Iterative function is: 4641.43
Variance using Iterative function is: 8.57314e+006
Standard deviation using Iterative function is: 2927.99
Running time for iterative function: 7 Milli Seconds
Mean using Recursive function is: 4641.43
Variation using Recursive function is: 8.57314e+006
Standard deviation using Recursive function is: 2927.99
Running time for Recursive function: 7 Milli Seconds
Want to see more full solutions like this?
Chapter 5 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
- By using java, Write a recursive function that finds the maximum element in an array ofintegers, based on comparing the first element in the array against themaximum in the rest of the array recursively.arrow_forwardFor function addOdd(n) write the missing recursive call. This function should return the sum of all postive odd numbers less than or equal to n. Examples: addOdd(1) -> 1addOdd(2) -> 1addOdd(3) -> 4addOdd(7) -> 16 public int addOdd(int n) { if (n <= 0) { return 0; } if (n % 2 != 0) { // Odd value return <<Missing a Recursive call>> } else { // Even value return addOdd(n - 1); }}arrow_forward1. Compute the recursive function f(n) = 3f(n–3)– l; ƒ(0) = 1; for n=12;. Show %3D %3D %3D clearly how the function is evaluated and the return of the function for every recursive step as seen in class. Show all your work to get creditarrow_forward
- Compute f(6) for the recursive function below. def f(n): if n == 0: return 1 if n == 1: return 2 else: return f(n-1)+n*f(n-2)-narrow_forwardiii. Let K be an integer and suppose F(K) is recursively defined by: F( int k) If (k==0) return 5 else return F(k-1)+2 Find and Trace F(7)arrow_forwardWrite recursive and iterative methods to compute the summation of following series: ao aj az az an 5 20 80 320 4an-1 For example: a, = 5, n = 4 public static double m(.. , ..) public static double iterative_m( .. , ..) ao + az + a, +az = 425arrow_forward
- Write the Fibonacci Function program with: Recursive and Iterative method respectively using the following condition: Fib (1) is 1 Fib (2) is 1 Fib (N) is Fib (N-2) + Fib (N-1), for N > 2 Show the Hand Simulations of activation records for both the programs and display the outputarrow_forwardWrite a recursive function that takes as a parameter a nonnegative integer and generates the following pattern of stars. If the nonnegative integer is 4, then the pattern generated is: **** *** ** * ** *** ****arrow_forwardLet n be a positive integer and let MaxCrossing(n) be a function that returns the maximum number of line crossings that you can create by drawing n straight lines. Write down a recursive formula for MaxCrossing(n) and analyze the time complexity of the corresponding recursive algorithm. You must write a formal recursive formula including the base case and general recursive step.arrow_forward
- Your main task is to write a recursive function sierpinski() that plots a Sierpinski triangle of order n to standard drawing. Think recursively: sierpinski() should draw one filled equilateral triangle (pointed downwards) and then call itself recursively three times (with an appropriate stopping condition). It should draw 1 filled triangle for n = 1; 4 filled triangles for n = 2; and 13 filled triangles for n = 3; and so forth. Sierpinski.java When writing your program, exercise modular design by organizing it into four functions, as specified in the following API: public class Sierpinski { // Height of an equilateral triangle with the specified side length. public static double height(double length) // Draws a filled equilateral triangle with the specified side length // whose bottom vertex is (x, y). public static void filledTriangle(double x, double y, double length) // Draws a Sierpinski triangle of order n, such that the largest filled //…arrow_forwardUse the recursion to solve the following problems 1. Calculate the sum of an array of n integers. 2. Compute Powers, p(x,n)=xn 3. Revers an array of n integers 4. Calculate the length of string (number of characters) 5. Implement the tail recursion for problems 1 and 2. Please test the program by using 2 different input sets!arrow_forwardWrite a recursive function called that takes a string of single names separated by spaces and prints out all possible combinations (permutations), each combination on a new line. When the input is: Alice Bob Charlie then the output is: Alice Bob Charlie Alice Charlie Bob Bob Alice Charlie Bob Charlie Alice Charlie Alice Bob Charlie Bob Alice Here is the original code in Python: def all_permutations(permList, nameList): # TODO: Implement method to create and output all permutations of the list of names. pass if __name__ == "__main__": nameList = input().split(' ') permList = [] all_permutations(permList, nameList)arrow_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education