Vectors and Vector Operations



1.10 Recursion

A recursive definition of a term is a definition that involves the term itself in the definition of the term.

A recursive formula (or recursive function) is a formula (or function) that involves itself in its definition.

A recursive function in a computer program is one that calls itself.

In the last two cases you need to be careful you don't get caught in an infinite loop. A classic example of recursion is the definition of factorials.

Example 1. Factorials. Recall that the factorial of a positive integer n is the product of all the integers from 1 to n, i.e.

n! = 1(2(3(…(n

For example

4! = 1(2(3(4 = 24

Many books make the special definition in the case that n = 0 by setting 0! = 1. In order to make this into a recursive definition, note that

n! = 1(2(3(…((n-1)(n = [1(2(3(…((n-1)] ( n = n [(n-1)!]

Thus

n! = n [(n-1)!]

Notice that this formula for n! involves a factorial on the right. It is this aspect that makes the formula recursive. However, this formula is not a complete definition of n!. We need to augment it by the special case where n = 0. So a complete recursive definition of n! would be the following.

(1) n! =

To use this definition to compute 4! we would proceed as follows. Putting n = 4 into the definition (1) we get

(2) 4! = 4((4-1)! = 4(3!

At this point we leave off the calculation of 4! and use the definition to compute 3!. Putting n = 3 into (1) gives

(3) 3! = 3((3-1)! = 3(2!

At this point we leave off the calculation of 3! and use (1) to compute 2!.

(4) 2! = 2((2-1)! = 2(1!

Now we use (1) with n = 1.

(5) 1! = 1((1-1)! = 1(0!

Now we use (1) with n = 0. However, in this case (1) simply says

0! = 1

We put this into (5) giving

1! = 1(0! = 1(1 = 1

We put this into (4) giving

2! = 2(1! = 2(1 = 2

We put this into (3) giving

3! = 3(2! = 3(2 = 6

Finally, we put this into (2) giving

4! = 4(3! = 4(6 = 24

The definition (1) can be used as the basis of a recursive function in a computer program. For example, in C one could convert (1) into the following.

int factorial( int n )

{ if (n == 0)

return 1;

else

return n * factorial( n – 1 );

}

The recursive computation of 4! above amounted to a loop. It turns out that in computer programming, many things that can be done with a loop can be done with a recursive function instead.

For comparison purposes, here is a function in C which computes n! using a loop instead of recursion.

int factorial( int n )

{ int j, nfact;

nfact = 1;

for (j = 1; j ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download