We want to write a function that counts the number of elements in a list that are
Question:
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. (1 mark) int Sum( NodeType* node ) { (b) Modify the above recursive function (introducing a single accumulator) to make it tail-recursive. (2 marks) 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. (3 marks) 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. (3 marks)
int TCount (NodeType* node,
Data Structures and Algorithms in Python
ISBN: 978-1118290279
1st edition
Authors: Michael T. Goodrich , Roberto Tamassia, Michael H. Goldwasser