5.3. Calculating the Sum of a Vector of Numbers¶
We will begin our investigation with a simple problem that you already
know how to solve without using recursion. Suppose that you want to
calculate the sum of a vector of numbers such as:
theSum
) to compute a running total of all the numbers in the vector
by starting with
Pretend for a minute that you do not have while
loops or for
loops. How would you compute the sum of a vector of numbers? If you were a
mathematician you might start by recalling that addition is a function
that is defined for two parameters, a pair of numbers. To redefine the
problem from adding a vector to adding pairs of numbers, we could rewrite
the vector as a fully parenthesized expression. Such an expression looks
like this:
We can also parenthesize the expression the other way around,
Notice that the innermost set of
parentheses,
How can we take this idea and turn it into a C++ program? First,
let’s restate the sum problem in terms of C++ arrays. We might say
the sum of the vector numVect
is the sum of the first element of the
vector (numVect[0]
), and the sum of the numbers in the rest of the array (numVect.erase(numVect.begin()+0)
).
In this equation
There are a few key ideas while using vector to look at. First, on line 6 we are checking to see if the vector is one element long. This
check is crucial and is our escape clause from the function. The sum of
a vector of length 1 is trivial; it is just the number in the vector.
Second, on line 11 our function calls itself! This is the
reason that we call the vectsum
algorithm recursive. A recursive
function is a function that calls itself.
Figure 1 shows the series of recursive calls that are
needed to sum the vector
When we reach the point where the problem is as simple as it can get, we
begin to piece together the solutions of each of the small problems
until the initial problem is solved. Figure 2 shows the
additions that are performed as vectsum
works its way backward
through the series of calls. When vectsum
returns from the topmost
problem, we have the solution to the whole problem.