6.1. What is Recursion?

Recursion refers to defining something in terms of itself. While recursion may appear in many forms (paintings and poems, for example), in computer science and mathematics, objects or functions exhibit recursive behavior when they can be defined by two properties:

Some famous sequences in mathematics, such as the Fibonacci sequence are generated recursively.

6.1.1. Accumulating a sum

Consider a problem you are already familiar with: computing the sum of a sequence of numbers.

The function accumulate loops over each element in the vector values.

The variable sum holds the running total.

When the loop completes, the total is returned.

If the vector is empty, then 0 is returned.

 1int accumulate(const std::vector<int>& values) {
 2  int sum = 0;
 3  for (const auto& x: values) {
 4    sum = sum + x;
 5  }
 6  return sum;
 7}
 8         
 9int main () {
10  std::vector<int> values = {1,2,3,4,5,6,7,8,9,10};
11
12  auto sum = accumulate(values);
13  std::cout << "sum is: " << sum << '\n';
14  
15  return sum;
16}

The implementation details are not critical here. We could have used a traditional for loop or a while loop and computed the same value. The point is that all these solutions are iterative.

It is possible to solve this problem without using a loop. Actually, there is a loop of sorts, but it is the function itself that is used as the looping construct. Let’s pick apart accumulating the sum to see how.

Recall that addition is a binary operation - an operation with two operands: a pair of numbers. We need to restate the accumulate problem from adding a vector to adding pairs of numbers.

\[1 + 2 + 3 + 4\]

Can be rewritten as:

\[(1 + (2 + (3 + 4)))\]

Notice that the innermost set of parentheses, \((3 + 4)\), is a problem that we can solve without a loop or any special constructs. In fact, we can use the following sequence of simplifications to compute a final sum.

\[\begin{split}total = \ (1 + (2 + (3 + 4))) \\ total = \ (1 + (2 + 7)) \\ total = \ (1 + 9) \\ total = \ 10\end{split}\]

How can we take this idea and turn it into a C++ program? First, let’s restate the sum problem in terms of a C++ vector. We might say the sum of the vector values is the sum of the first element of the vector (values[0]), and the sum of the numbers in the rest of the vector - the range values.begin()+1 to values.end().

Instead of a local variable to accumulate the sum, the return value of the function stores the accumulated sum.

Each return value is the current first elment of the vector plus a slice of the vector composed of all the elements after the first element.

The base case occurs when the vector is empty - there is nothing left to add. We return zero since no matter what is in the vector, adding zero does not change the final result.

If the container is not empty, then it must contain at least one element. The recursive case is then the first element, plus everything after the first element (which might be nothing).

 1int accumulate(const std::vector<int>& values) {
 2  // base case
 3  if (values.empty()) return 0;
 4  
 5  // recursive case
 6  auto slice = std::vector<int>(values.begin()+1, values.end());
 7  return values[0] + accumulate(slice);
 8}
 9         
10int main () {
11  std::vector<int> values = {1,2,3,4,5,6,7,8,9,10};
12
13  auto sum = accumulate(values);
14  std::cout << "sum is: " << sum << '\n';
15  
16  return sum;
17}

Run both the iterative an recursive versions and verify they both produce the same results.

The recursive calls to accumulate perform in code the same steps outlined when we grouped the addition sequence using parentheses.

More to Explore

You have attempted of activities on this page