Recursive Function is a function that repeats or uses its own previous term to calculate subsequent terms and thus forms a sequence of terms. Usually, we learn about this function based on the arithmetic-geometric sequence, which has terms with a common difference between them. This function is highly used in computer programming languages, such as C, Java, Python, PHP. In this article, we will discuss the definition of a recursive function, its formula, and the procedure of creating the recursive formula for the given sequence with solved examples.
Table of Contents:
- Recursion Definition
- Recursively Defined Functions
- What Makes the Function Recursive
- Formula
- Recursive Formula for Arithmetic Sequence
- Recursive Formula for Geometric Sequence
- Solved Problems
- Points to Remember
- Practice Problems
- FAQs
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 a1,a2,a3,a4,…..,an,… 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 an.
i.e. an=an-1+a1
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;
an= r × an-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:
an = an-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 an = an-1 + 2.
Explanation:
Here, a1 = 2
Thus, a2 = a(2-1)+2 = a1+2 =2+2 = 4
a3 = a(3-1) +2 = a2+2=4+2 = 6
a4 = a(4-1) +2 = a3+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. an-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. an-1.
Explanation:
Here, a1 = 3
Thus, a2 = a(2-1).5 = a1.5 =3(5) = 15
a3 = a(3-1) .5= a2.5=15(5) = 75
a4 = a(4-1) .5= a3.5=75(5) = 375, and the process continues.
Recursive Function Example
Example 1:
Let a1=10 and an = 2an-1 + 1
So the series becomes;
- a1=10
- a2=2a1+1=21
- a3=2a2+1=43
- a4=2a3+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:
a1=3, an=2.an-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.
Practice Problems on Recursive Function
Solve the following problems on recursive function:
- Find the recursive formula for the sequence: 4, 8, 12, 16, 20, 24, 28, …
- Find the recursive formula in function notation for the sequence: 5, 10, 15, 20, 25, …
Frequently Asked Questions on Recursive Function
What is meant by recursive function?
The function that uses the previous term to find the next term in the sequence is called a recursive function.
Mention the two parts used in the recursive function formula?
The recursive function has two parts. The first part is the definition of the smallest argument and the second part is the definition of the nth term.
What is the recursive function of the Fibonacci sequence?
The recursive function of Fibonacci sequence is
f(n)=f(n-2)+f(n-1)
Where f(1)=1, f(2)= 1
What is the recursive function formula for the sequence 1, 1, 2, 6, 24, 120?
The recursive function for the sequence 1, 1, 2, 6, 24, 120 is f(n)= n. f(n-1), where f(0)=1.
How to write the recursive formula?
The recursive formula is written based on the first term, successive terms and the common difference or common ratio of the sequence.
Study, related topics on recursive function by downloading BYJU’S- The Learning App and get interactive videos.
Comments