Recursively defined functions

What is Recursion?

When a recursive procedure gets repeated, it is called recursion. A recursive is a type of function or expression stating some concept or property of one or more variables, which is specified by a procedure that yields values or instances of that function by repeatedly applying a given relation or routine operation to known values of the function.

Or

A function which calls itself from its previous value to generate subsequent value.

Or

A function that calls itself during its execution.

You can understand the concept of recursion by taking a real-life example. Suppose you are taking a staircase to reach from ground floor to the first floor. So you take steps one by one here. You can reach the second step only when you have stepped first. Again to reach the third step, you have to take the second step first. This is the process of repetition. With each next step, you are adding previous steps as a repeated sequence with a common difference between each step. This is the meaning of recursive.

Step 2 = Step 1 + ground floor

Step 3 = Step 2 + step 1 + ground floor

And so on.

The most common example we can take is the set of natural numbers, which start from one goes till infinity, i.e. 1,2,3,4,5,6,7, …., ∞ .  Therefore, in the sequence of natural number, each term has a common difference between them as 1, which means each time the next term calls its previous term to get executed.

What is a Recursively Defined Function?

For any recursively defined function, it has two parts. The first part is the definition of the smallest argument and the second part is the definition of the nth term. The smallest argument is usually denoted by f(0) or f(1) and the nth argument is denoted by f(n).  

Now, let us understand the recursively defined function with the help of an example.

Let the sequence be 5, 7, 9, 11

The explicit formula for the given sequence is f(n)= 2n+5

The recursive formula for the given sequence is given by

f(0)= 5

f(n) = f(n-1)+2

Now, we can check the sequence terms using the recursive formula as follows:

f(0)= 5

f(1) = f(0)+2

f(1)= 5+2 = 7

f(2) = f(1)+2 

f(2)= 7+2 =9

f(3)= f(2)+2

f(3)= 9+2 = 11

In this way, we can find the next term in the sequence with the help of the recursive function formula.

What Makes the Function Recursive?

To make the function recursive, it requires its own term to figure out the next term in the sequence. For example, if we want to find out the nth term in the sequence, we need to know the previous term and also the term before the previous term. Hence, we need to know the previous term to determine whether the sequence is recursive or not recursive. So we can say that, if the function requires the previous term to find the next term in the sequence, then the function is a recursive function. Most of the recursive functions will provide the beginning value of the sequence and the formula that helps to generate the next terms in the sequence.

Recursive Function Formula

If a₁,a₂,a₃,a₄,…..,a_n,… is a set of series or a sequence. Then a recursive formula for this sequence will require to compute all the previous terms and find the value of a_n.

i.e. a_n=a_n-1+a₁

This formula can also be defined as Arithmetic Sequence Recursive Formula. As you can see from the sequence itself, it is an Arithmetic sequence, which consists of the first term followed by other terms and a common difference between each term is the number you add or subtract to them.

A recursive function can also be defined for a geometric sequence, where the terms in the sequence have a common factor or common ratio between them. And it can be written as;

a_n= r × a_n-1

Generally, the recursive function is defined in two parts. It a statement of the first term along with the formula/ rule related to the successive terms.

How to Write a Recursive Formula for Arithmetic Sequence?

Go through the following steps to find the recursive formula for the arithmetic sequence:

Step 1: Determine whether the given sequence is arithmetic. (Add or subtract the two successive terms. If we get the same amount from one term to the next term, then the sequence is arithmetic).

Step 2: Find the common difference of the given sequence. 

Step 3: Formulate the recursive formula by stating the first term, and then create the formula to be the previous term + common difference.  

Thus, the recursive formula for the arithmetic sequence is given as: 

a_n = a_n-1 + d

Consider the sequence: 2, 4, 6, 8, 10, …

The above sequence is an arithmetic sequence because each term in the sequence is increased by 2. Hence, the common difference is 2. Thus, the recursive formula for the sequence is a_n = a_n-1 + 2.

Explanation: 

Here, a₁ = 2

Thus, a₂ = a_(2-1)+2 = a₁+2 =2+2 = 4

a₃ = a_(3-1) +2 = a₂+2=4+2 = 6

a₄ = a_(4-1) +2 = a₃+2=6+2 = 8, and the process continues.

How to Write a Recursive Formula for Geometric Sequence?

Go through the following steps to find the recursive formula for geometric sequence:

Step 1: Determine whether the given sequence is geometric. (Multiply or divide each term by a number. If we get the same amount from one term to the next term, then the sequence is geometric.)

Step 2: Find the common ratio of the given sequence. 

Step 3: Formulate the recursive formula by stating the first term, and then create the formula to be the common ratio to the previous term. 

Thus, the recursive formula for the geometric sequence is given as: 

an = r. a_n-1 

Consider the sequence: 3, 15, 75, 375, …

The above sequence is a geometric sequence because the successive term in the sequence is obtained by multiplying 5 to the previous term. Hence, the common ratio is 5. Thus, the recursive formula for the sequence is an = 5. a_n-1.

Explanation: 

Here, a₁ = 3

Thus, a₂ = a_(2-1).5 = a₁.5 =3(5) = 15

a₃ = a_(3-1) .5= a₂.5=15(5) = 75

a₄ = a_(4-1) .5= a₃.5=75(5) = 375, and the process continues.

Recursive Function Example

Example 1:

Let a₁=10 and a_n = 2a_n-1 + 1

So the series becomes;

• a₁=10
• a₂=2a₁+1=21
• a₃=2a₂+1=43
• a₄=2a₃+1=87
• and so on.

Example 2:

Find the recursive formula for the sequence 3, 6, 12, 24, 48, 96.

Solution:

Given sequence, 3, 6, 12, 24, 48, 96,…

The given sequence is a geometric sequence because if the preceding term is multiplied by 2, we get the successive terms.

To find the recursive formula for the given sequence, write it in the tabular form.

Term Numbers	Sequence Term	Function Notation	Subscript Notation
1	3	f(1)	a1
2	6	f(2)	a2
3	12	f(3)	a3
4	24	f(4)	a4
5	48	f(5)	a5
6	96	f(6)	a6
n	. .	f(n)	an

Hence, the recursive formula in function notation is given as:

f(1) = 3 , f(n)= 2. f(n-1)

In subscript notation, the recursive formula is given by:

a₁=3, a_n=2.a_n-1

Points to Remember to Derive the Recursive Formula

• Recursive functions call their own function for succeeding terms.
• Always check the type of sequence whether it is arithmetic or geometric, which means the number is added or subtracted in the next term of the sequence with a common difference or they are multiplied and have a common factor between them respectively.
• Find out the common difference for arithmetic series and the common factor for geometric series between each term in the sequence respectively.
• Then write the recursive formula based on the first term and successive terms and the common difference or common factor between them for both the series.