 # 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.

1. What is the seed value in a recursive function?

The first value of the series which is needed to be stated to find the remaining values of the series is also called the seed value. For example in series 3, 5, 7,… the seed value is 3 (first value of the series)

2. Why is the Fibonacci series a special case of recursive function?

A Fibonacci series is a special series that does not fall into either arithmetic or geometric sequence. The series will look like this: 0, 1, 1, 2, 3, 5, 8… Here, after the first 2 values in the series, the rest of them are derived by adding the previous 2 numbers. So this series has 2 seed values f(0) = 1 and f(1) = 1. The pattern or rule for the other numbers is; f(n) = f(n-1) + f(n-2)

3. Who first gave the formula for recursive function?

Dedekind first used the notion of recursion in 1888 when he was analyzing natural numbers. The first work which was dedicated exclusively to the concept of recursion was done in 1924 by Norwegian Thoralf Albert Skolem, who was a pioneer in Metalogic. He developed this to avoid the paradoxes of the infinite.

4. How is the recursive function used in computer programming?

Recursive methods are an elegant way to do some repetitive task in many programming languages like C#, Java, PHP, etc. Recursion can be used to solve the problem only if it can be broken down into small parts. An iterative method can be too complicated for such tasks; hence recursive methods are used. For example, searching through a file system can be done using recursion.