Recursive Average
Problem
Write a recursive algorithm to compute the average of an array of numbers.
Solution
The average of an array of numbers is the sum of all numbers divided by the total number of elements. It is the same as dividing each number by the total number of elements then adding each division result to get the final average value. For example Avg(A) = (A[0] + … + A[n-1])/n = A[0]/n + … + A[n-1]/n As you can see it is almost the same formula as the recursive sum problem that we solved before except we are dividing by (n)
Recursive Average Algorithm
Here is the code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Includes #include <iostream> //STD using namespace std; float RecursiveAvg(float A[], int i, int n) { //Base case if (i == n-1) return A[i]/n; return A[i]/n + RecursiveAvg(A, i + 1, n); } //Main function void main() { float A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; cout << RecursiveAvg(A, 0, 10) << endl; } |
Solution
We can compute the average recursively using the concept of running average. If we have already calculated the average of some elements then the average when adding one more element to the list is calculated by adding the element to the product of the old average with number of elements before addition divided by the current total number of elements
Code
Here is the code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Includes #include <iostream> //STD using namespace std; float RecursiveAvg(float A[], int i, int n) { //Base case if (i == n-1) return A[i]; return (A[i] + (n-i-1) * RecursiveAvg(A, i + 1, n))/(n-i); } //Main function void main() { float A[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; cout << RecursiveAvg(A, 0, 10) << endl; } |
Thanks for visiting.
About Author
Mohammed Abualrob
Software Engineer @ Cisco