递归在数组求平均代码中的执行逻辑与调用顺序问询

Question #

I'm trying to understand how recursion works. I've grasped simple recursive examples like factorial, but I can't wrap my head around how halfOne and halfTwo are assigned recursively in this array average code. I want to know the call order and execution logic here—any help would be greatly appreciated!

Here's the code:

#include <iostream>
using namespace std;
const int SIZE = 5;
double average(int nums[], int left, int right, double len);
int main() {
    int nums[SIZE];
    int left, right;
    double len;
    //If len was an int, the average would always be zero
    double avg = 0;
    //These are for testing
    long double testNum = 0;
    long double testAvg;
    //Populate the array with random integers from 1 - 100
    for (int i = 0; i < SIZE; i++) {
        nums[i] = (rand() % 100) + 1;
        testNum = testNum + nums[i]; //For Testing
    }
    left = 0;
    right = SIZE - 1;
    len = right - left + 1;
    //For computing the average
    avg = average(nums, left, right, len);
    testAvg = testNum / SIZE; //To test my function
    cout << "Average from assignment: " << testAvg << endl;
    cout << "Average from function: " << avg << endl;
    int x;
    cin >> x;
    return 0;
}
//This function will find the average of all the numbers in an array
//By summing together every number divided by the total len.
//This works because (1 + 2 + 3)/3 is equal to (1/3) + (2/3) + (3/3)
double average(int nums[], int left, int right, double len) {
    double halfOne, halfTwo;
    //This is the base case which will be evaluated
    if (left == right)
        return (nums[left] / len);
    //The array is split until it is of the size 1
    //And each element is evaluated with the base case
    halfOne = average(nums, left, (left + right) / 2, len);
    halfTwo = average(nums, (left + right + 2) / 2, right, len);
    //Each half is added together to get the final total average.
    return (halfOne + halfTwo);
}

Answer #

Great question—this is a classic divide-and-conquer recursion example, which is a bit trickier than factorial because it splits the problem into two subproblems instead of one. Let's break this down step by step, using the SIZE = 5 example from your code to make it concrete.

First, let's recap the core idea the comment mentions: instead of calculating (sum of all elements) / total length, it calculates (element1/len) + (element2/len) + ... + (elementN/len). The recursion just splits the array into smaller chunks to compute these fractions and add them up.

1. Base Case: The Termination Condition

The base case if (left == right) triggers when we're looking at a single element in the array. At this point, we just return that element divided by the total length of the original array (not the length of the small chunk!). That's key—every single element contributes its own nums[i]/len to the final average.

2. Recursive Splitting: How halfOne and halfTwo Work

Let's use an example array (say nums = [10, 20, 30, 40, 50], len = 5) to trace the call order:

• First Call: average(nums, 0, 4, 5)
  Since left != right, we first compute halfOne by calling average(nums, 0, (0+4)/2=2, 5).

  • Second Call (halfOne branch): average(nums, 0, 2, 5)
    Again, left != right, so we call average(nums, 0, (0+2)/2=1, 5) for halfOne here.

    • Third Call (halfOne of halfOne): average(nums, 0, 1, 5)
left != right, call average(nums, 0, (0+1)/2=0, 5) for halfOne.

      • Fourth Call (base case): average(nums, 0, 0, 5)
left == right, returns 10/5 = 2.0. Now this value is assigned to the halfOne in the third call.

      • Now the third call moves to compute halfTwo: average(nums, (0+1+2)/2=1, 1, 5)
        This is another base case, returns 20/5 =4.0. Assign to halfTwo in the third call.

      • Third call returns 2.0 +4.0 =6.0—this becomes the halfOne value in the second call.

    • Second call now computes halfTwo: average(nums, (0+2+2)/2=2, 2,5)
      Base case, returns 30/5=6.0. Assign to halfTwo in the second call.

    • Second call returns 6.0 +6.0=12.0—this is the halfOne value in the first call.

  • Now the first call moves to compute halfTwo: average(nums, (0+4+2)/2=3,4,5)

    • Fifth Call (halfTwo branch): average(nums,3,4,5)
left != right, call average(nums,3,(3+4)/2=3,5) for halfOne.

      • Sixth Call (base case): average(nums,3,3,5) returns 40/5=8.0—assigned to halfOne in fifth call.

      • Fifth call computes halfTwo: average(nums,(3+4+2)/2=4,4,5) returns 50/5=10.0—assigned to halfTwo.

      • Fifth call returns 8.0+10.0=18.0—this is the halfTwo value in the first call.

• First Call Final Return: 12.0 +18.0=30.0—which is exactly the average of [10,20,30,40,50] (150/5=30). Perfect!

3. Key Observations About Call Order

• The recursion fully resolves the halfOne branch first before even starting on halfTwo. That means it dives all the way down the left side of the array split until it hits a base case, then backtracks up, then moves to the right branch.
• Every recursive call uses the original len (total array size), not the size of the current chunk. That's why each base case returns nums[i]/len instead of nums[i]/chunk_size—summing all these gives the correct average.
• The split logic (left+right)/2 and (left+right+2)/2 ensures that even with odd-sized arrays (like 5 elements), we split into [0-2] and [3-4]—no elements are missed or duplicated.

4. Why This Works

Since average is a linear operation, (a+b+c+d+e)/5 = a/5 + b/5 + c/5 + d/5 + e/5. The recursion just breaks the array into smaller groups, computes the sum of their individual element/len values, and adds those group sums together. It's the same as adding all the fractions directly—just split into steps via recursion.

Hopefully this step-by-step trace makes the call order and logic click! Let me know if you want to walk through another scenario.

内容的提问来源于stack exchange，提问作者Süleyman Acar