C++ Data Structures Course about Recursion We want to write a function that coun
ID: 3853216 • Letter: C
Question
C++ Data Structures Course about Recursion
We want to write a function that counts the number of elements in a list that are larger than the average. For example, the function should return 2 for list {1, 2, 3, 4}, since two elements are above 2.5 (the average), and it should return 1 for list {3, 1, 2, 10}, since only the last element is above 4. An iterative version of this function is trivial to code but also inefficient, as it will need to traverse the list twice: first to calculate the average then to compare and count elements. However, we can write an accumulator recursive version of this function that will traverse the list only once! To do this, follow the detailed steps below in order. Assume we use the usual NodeType structure and ItemType class to define a linked list of integers. (a) Write the plain recursive function below (not tail-recursive) that returns the sum of all integer elements in the list. int Sum(NodeType* node) { ((b) Modify the above recursive function (introducing a single accumulator) to make it tail-recursive. int TSum(NodeType* node, (c) Amend the above tail-recursive function (using another accumulator) so that it returns the average of all integer elements in the list. int TAvg(NodeType* node, (d) Adapt the above function so that it returns the number of elements in the list that are larger than the average. The figure below is a hint. int TCount(NodeType* node,Explanation / Answer
a.
int Sum(NodeType * node)
{
if(!node)
return 0;
else
return (*node)+Sum(node->next);
}
b.
int Sum(NodeType * node)
{
return TSum(node,0);
}
int TSum(NodeType* node,int sum)
{
if(!node)
return sum;
else
return (node->next,(*node)+sum);
}
c.
int Avg(NodeType * node)
{
return TAvg(node,0,0,0);
}
int TAvg(NodeType* node, int sum, int count,int avg)
{
if(!node)
return avg;
else
return TAvg(node->next,(*node)+sum,count++,sum/count);
}
d.
int Count(NodeType* node)
{
return TCount(node,0,0,0,0);
}
int TCount(NodeType* node,int sum,int count,int avg,static int countLarge)
{
int average;
if(!node)
return avg;
else
{
average=TCount(node->next,(*node)+sum,count++,sum/count,0);
if((*node)>average)
countLarge++;
return average;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.