Recursive Definitions

Read this article to learn the basics of recursion.


A recursive definition of a function defines its values for some inputs in terms of the values of the same function for other inputs.

LEARNING OBJECTIVE

  • Use a recursive formula to find specific terms of a sequence

KEY POINTS

  • In mathematical logic and computer science, a recursive definition, or inductive definition, is used to define an object in terms of itself.
  • The recursive definition for an arithmetic sequence is: an=an1+d . The recursive definition for a geometric sequence is: an=r⋅an−1 .

Recursion

In mathematical logic and computer science, a recursive definition, or inductive definition, is used to define an object in terms of itself. A recursive definition of a function defines values of the function for some inputs in terms of the values of the same function for other inputs. 

For example, the factorial function n! is defined by the rules:

0!=1

(n+1)!=(n+1)n!

0 ! = 1

( n + 1 ) ! = ( n + 1 ) n !

This definition is valid because, for all n, the recursion eventually reaches the base case of 0.

For example, we can compute 5! by realizing that 5!=54!, and that 4!=43!, and that 3!=32!, and that 2!=21!, and that: 

1!=10!

=11

=1

Putting this all together we get: 

5!=54321=120

5 ! = 5 4 3 2 1 = 120

Recursive Formulas for Sequences

When discussing arithmetic sequences, you may have noticed that the difference between two consecutive terms in the sequence could be written in a general way:

an=an1+d

The above equation is an example of a recursive equation since the nth term can only be calculated by considering the previous term in the sequence. Compare this with the equation:

an=a1+d(n1).

In this equation, one can directly calculate the nth-term of the arithmetic sequence without knowing the previous terms. Depending on how the sequence is being used, either the recursive definition or the non-recursive one might be more useful.

A recursive geometric sequence follows the formula: 

an=ran1

An applied example of a geometric sequence involves the spread of the flu virus. Suppose each infected person will infect two more people, such that the terms follow a geometric sequence.

Image describing spread of flu from original host

The flu virus is a geometric sequence

Each person infects two more people with the flu virus, making the number of recently-infected people the nth term in a geometric sequence.

Using this equation, the recursive equation for this geometric sequence is: 

an = 2 an1

a n = 2 a n 1

Recursive equations are extremely powerful. One can work out every term in the series just by knowing previous terms. As can be seen from the examples above, working out and using the previous term a n 1 can be a much simpler computation than working out a n from scratch using a general formula. This means that using a recursive formula when using a computer to manipulate a sequence might mean that the calculation will be finished quickly.


Source: BlueBox 
Creative Commons License This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.

Last modified: Thursday, August 17, 2023, 5:59 AM