9.5 Recursion

I l @ ve RuBoard

Recursion occurs when a function calls itself directly or indirectly. Some programming functions lend themselves naturally to recursive algorithms, such as the factorial.

A recursive function must follow two basic rules:

• It must have an ending point.

• It must reduce the amount of work to be done each time it's called.

A definition of factorial is:

 fact(0)  = 1  fact(n)  = n * fact(n-1) 

In C++, this definition translates to:

 int fact(int number)  {      if (number == 0)          return (1);      /* else */      return (number * fact(number-1));  } 

This satisfies the two rules. First, it has a definite ending point (when number == 0 ). Second, it reduces the amount of work to be done because computing fact(number-1) is simpler than fact(number) .

Factorial is legal only for number >= 0 . But what happens if we try to compute fact( -- 3) ? The program aborts with a stack overflow or similar message. fact( -- 3) calls fact( -- 4) calls fact( -- 5) and so on. There is no ending point. This is called an infinite recursion error . In this case it was caused by a bad parameter. We should check for that:

 int fact(int number)  {      assert(number >= 0);     if (number == 0)          return (1);      /* else */      return (number * fact(number-1));  } 

Many things we do iteratively can be done recursively, like summing the elements of an array. You can define a function to add elements m through n of an array as follows :

If you have only one element, the sum is simple.

Otherwise, it is the sum of the first element and the sum of the rest.

In C++ this is:

 int sum(const int first, const int last, const int array[],          const int array_size)  {      assert((first > 0) && (first < array_size));     assert((last > 0) && (last < array_size));     if (first == last)          return (array[first]);      /* else */          return (array[first] + sum(first + 1, last, array));  } 

For example:

Sum(1 8 3 2) =

1 + Sum(8 3 2) =

8 + Sum(3 2) =

3 + Sum(2) =

2

3 + 2 = 5

8 + 5 = 13

1 + 13 = 14

Answer = 14

This is not to say that this is the clearest or fastest way to sum a loop. In this case, a loop would be much faster. But it does illustrate how recursion can be used to create a nontraditional solution to a problem.

I l @ ve RuBoard