recusrive_mean.cpp

#include <vector>
#include <utility>
#include <cstdio>


std::pair<float, int> recursive_mean(
    const std::vector<float> &vec,
    const int first,
    const int last) {

    float mean = 0;
    int count = 0;

    if (last <= first) {
        return std::make_pair(mean, count);
    }

    if (last == first + 1) {
        mean = vec[first];
        count = 1;
    } else {
        const int mid = first + (last - first) / 2;
        auto left_result = recursive_mean(vec, first, mid);
        auto right_result = recursive_mean(vec, mid, last);

        count = left_result.second + right_result.second;

        float left_scale = float(left_result.second) / float(count);
        float right_scale = float(right_result.second) / float(count);

        mean = left_result.first * left_scale + right_result.first * right_scale;
    }
    return std::make_pair(mean, count);
}


int main() {
    std::vector<float> vec(9, 5.5);
    auto result = recursive_mean(vec, 0, vec.size());
    printf("Mean: %g\n", result.first - vec[0]);

    return 0;
}