Recursive Functions in R

Recursion is one of the most important aspects of any programming language. Not only because it saves you from the sophisticated looping, but also since it improves the efficiency of the code. The R programming language also supports this programming concept, and we will be discussing it in depth throughout this article.

 

Recursion: What is it?

 

There comes a time in programming, when the given function calls itself to repeat the task provided. This process of function calling itself is known as the recursion in R. It is similar to looping, however faster than the loops (in terms of processing).

 

Recursive Function: What does that mean?

 

A function that supports the concept of recursion, i.e., a function that calls itself considered as a recursive function in R. They are like loops, however more efficient than loops.

 

Why recursive functions and not the loops?

 

Well, every time we run a loop, a particular portion of computer memory in the local environment gets acquired. Moreover, it requires more time to get executed as it is checking each condition one by one and storing the logical responses in memory. However, with functions, the case is a bit easy. Once we execute any function, the memory it has acquired will immediately be released. Meaning, the memory gets freed once the function gets executed. Therefore, when a recursive function gets executed, the same thing happens that leads to the freeing up of the memory and saving the time by increasing the speed of execution (since we are using a function instead of a loop).

 

Applications of Recursion

 

Well, where could we use the recursion, you will ask. You will use recursion under dynamic programming in R. Dynamic programming allows us to reduce the recomputation and is also an essential tool for statistical analysis and computing. It is a vital part of top-down as well as bottom-up dynamic programming. Moreover, it is also crucial for divide and conquers algorithms within which we try to divide the entire program to the sub-parts so that the codes are more comfortable to solve.

 

Let us see some examples associated with the recursion in R programming.

 

Finding Factorial of any given natural number

 

A mathematical formula for the finding out factorial of any number is as given below:

n! = n * (n - 1) * (n - 2) * (n - 3) * … * 1

Meaning 5! = 5*4*3*2*1 = 120. Or in other language, 5! = 5 * 4!. We will use the same logic to build a factorial function under R.

 

Well, we can do this task in R programming. May be used for loop or using a while loop. However, if you see the pattern of this factorial, it is repetitive. If we use the for loop or a while loop, it will reduce the speed of execution. Instead of that, we can use define a recursive function that does the same task for us, and since it will be a function, the speed of execution will be more than the loops.

 

Let us define a recursive function for finding out the factorial of any natural number.

---

Example code with output for the factorial (recursive) function in R

---

Well, let us break down and understand this code more precisely for a better understanding.

 

Here, we wanted to find out the value for factorial 5, i.e., 5!. 

 

The function num_fact(5) starts executing and check if the number is zero or one since it is not zero or one, it mover further and runs the if-else part of the code. 

• We have function as num_fact(num) = num * num_fact(num - 1)

• Thus, num_fact(5) = 5 * num_fact(4) #Recursion happens here (repeating fun.)

• num_fact(5) = 5 * 4 * num_fact(3) #Recursion again

• num_fact(5) = 5 * 4 * 3 * num_fact(2) #Third step of recursion.

• num_fact(5) = 5 * 4 * 3 * 2 * num_fact(1) #Forth step of recursion

• num_fact(5) = 5 * 4 * 3 * 2 * 1 = 120 # Final answer.

 

If you see, the function num_fact gets repeated (recursed) under the code itself where we define it. Which leads us to the recursion, and finally, the output returned as expected.

 

Note: If the number is zero or one, the function will return a value one as initiated at the time of defining the same. 

 

 

Creating a Recursive Function that sorts a given vector

 

We can also create a function that can sort a given vector in either order (which we define, obviously). This function will take the first element of the given vector and create two other vectors, namely larger and smaller. These vectors will contain a single component, which is either larger or lower than the first item. These newly defined vectors will be further sorted using the same function, and finally, the system will arrange those in either order (ascending or descending).

 

See the example code for this function, as shown below:

---

Example code with output for the recursive function to sort a vector

---

Well, in this example, if we try to analyze the code above - 

 

• The function sort_vect takes an initial element from the vector and then compares it with the rest of the elements. 

• Now, the function stores the compared elements in two vectors greater and smaller. These two vectors contain the values greater than the initial element and lesser than the initial element respectively.

• The function recurses and chooses the greatest among all and the smallest among all (sorting the vector). This step continues until the last element of the vector is reached and the entire vector is sorted. Remember, the function inputs these values into greater and smaller vectors respectively.

• The function then arranges the elements of this vector into ascending or descending order. Here we have used (smaller, initial_element, greater) as an order which is ascending. You can modify the same to descending by using (greater, initial_element, smaller) as an order under the return() clause and returns the output.

---

Example code with output for sorting vector elements in descending order using recursion

---

See the example code with output above for the better realization of the element orders and how they can be tweaked in R while using this recursive function that order the vector elements for any given vector.

 

Conclusion

 

• This article emphasizes the importance, need, and application of recursion in R programming language with some hands-on examples where recursion is pretty useful over the normal looping functions.

• Recursion is a process in which the function repeats itself to complete the task provided and a function that does so is known as a recursive function.

• Recursion allows a programmer to break a big code chunk into small pieces and hence improving the efficiency and reducing the complexity of the given code

• Recursive functions are fast in working over the loops and this makes them more efficient for use over the loops in cases where it applies.

 

We also have seen some examples where the most common example is creating a factorial function that can give us the factorial value of any natural number. We also tried to get a unique function that could sort the elements of the given vector in either descending or ascending order based on the concept of recursion.

 

We will stop here in this article and in the next article will come up with some more interesting articles over a topic in R programming. Until then, stay safe! Keep learning! :)