Recursive Functions

Recursion is a process of defining objects based on previously defined other objects of the same type. A recursion relation defines some rules and a few initial values to build up an entire class of objects. Here it must be noted that if an object is defined in terms of itself, it causes self-recursion and leads to infinite nesting. A real-world example of recursion is when you are climbing a ladder. To reach the 3rd rung of the ladder, you need to reach the 2nd rung. Basically, it means that completing each step is dependent on the completion of the previous rung. 

Recursive Function Definition – When a function calls itself and uses its own previous terms to define its subsequent terms, it is called a recursive function. It is the technical recursive function’s definition, i.e., a recursive function builds on itself.

The Recursive Function has 2 parts:

• The value of the smallest or the first term in the sequence, usually given as f(0) or f(1)

• The pattern or the rule which can be used to get the value of any term, given the value of the term preceding it. In other words, the definition of f(n) when values of f(n-1), f(n-2), etc are given.

We will now explore this by looking at the recursive function example below:

We are given a sequence of numbers 3, 5, 7, 9…

a(1) = 3 –> the first term in the series

a(n) = a(n-1) + 2 -> The rule or pattern where you need to add 2 to the last term to get the next term in the series.

So in order to find say the 6th term, we would need to find all the terms before that as shown below:

A(1) = 3

A(2) =A (1) + 2 = 3 + 2 = 5

A(3) =A (2) + 2 = 5 + 2 = 7

A(4) =A (3) + 2 = 7 + 2 = 9

A(5) =A (4) + 2 = 9 + 2 = 11

A(6) =A (5) + 2 = 11 + 2 = 13

What makes this function recursive is that it needs to know its own terms to figure out its next terms. 

Expanding the recursive function formula for Arithmetic Progression – The process of defining a recursive formula for an arithmetic progression can be done by carrying below 

mentioned steps:

• You must determine that it is an arithmetic sequence, which means you either add or subtract the same constant value from one term to get the next term.

• Find the number that you add or subtract, or the common difference between consecutive terms

• Now the recursive formula can be created by stating 

• The first term

• The formula which involves the previous term and the common difference.

• So it looks like this: 

• a1 -> first term of the series

• an = an-1 + d, 

• here an-1 is the previous term, d is the common difference, an is the nth term in the series, and n the ordinal number of the term

The recursive formula for a geometric sequence – It is easier to create recursive formulas for most geometric sequences than an explicit formula. In this, the common ratio can be seen easily and can be used to create the recursive formula quickly. Let us look at a recursive function example for geometric series:

3, 6, 12, 24…

Here we can see that the first term is a1 = 3 and an = 2*an-1

Now we will look at the method to write a recursive function for a geometric series: 

• You must determine that it is a geometric sequence, which means you either multiply or divide the same constant value from one term to get the next term.

• Find the number that you multiply or divide by or the common ratio between consecutive terms

• Now the recursive formula can be created by stating 

• The first term

• The formula which involves the previous term and the common ratio.

• So it looks like this: 

• a1 -> first term of the series

• an = r * an-1

• here an-1 is the previous term, r is the common ratio, an is the nth term in the series, and n the ordinal number of the term

Visualization of Recursive Function – A Pascal’s triangle is the most famous example of a recursive sequence. In this, you can see that each term is obtained by adding 2 other parts of the triangle. Below is a visualization of the triangle:

Conclusion - A recursive function is a function that builds by calling itself and is calculated using a starting value and a pattern or rule which gives the next value in the series. It can be applied to arithmetic as well as geometric series. A common difference is used to add or subtract for getting the next term in an arithmetic progression, and a common ratio is used to multiply or divide to get the next term in a geometric progression. These functions are widely used in coding algorithms where one needs to traverse hierarchies or find the factorial of a number.