{"id":75753,"date":"2020-01-24T10:23:15","date_gmt":"2020-01-24T04:53:15","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=75753"},"modified":"2020-01-24T10:23:15","modified_gmt":"2020-01-24T04:53:15","slug":"recursion-in-r","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/recursion-in-r\/","title":{"rendered":"What is Recursion and Recursive Function in R Programming?"},"content":{"rendered":"

In the R functions<\/a> <\/strong>tutorial, we briefly looked at recursive functions. Now, in this article, we will cover their full scope. We will study the concept of recursion<\/strong> in programming languages. We will learn what recursive functions are. And also learn where recursive functions are useful through a few examples. This tutorial is surely going to be very interesting, so, get ready!<\/p>\n

What is Recursion in R?<\/h2>\n

Recursion, in the simplest terms, is a type of looping technique<\/strong>. It exploits the basic working of functions in R. We can call a function, declared in the global environment<\/strong> of the R session, from the global environment or the function\u2019s local environment<\/strong>.<\/p>\n

Recursion in R is when the function calls itself<\/strong>. This forms a loop, where every time the function is called, it calls itself again and again.<\/p>\n

What are Recursive Functions?<\/h3>\n

Recursive functions<\/strong> are functions that use the concept of recursion to perform repetitive or iterative tasks. They call themselves, again and again, this imitates a loop.<\/p>\n

Recursive functions need a stopping condition<\/strong> so that they do not keep looping indefinitely.<\/p>\n

Why use Recursive Functions?<\/h3>\n

Loops increase the memory and time requirements of any program. There are many cases where using a recursive function is a better alternative than using a loop. Once a function has returned its output, its local environment is destroyed along with any temporary variables and other memory allocations. This frees up the memory used by the function.<\/p>\n

The same goes for recursive functions. As soon as they return the output, their local environments are destroyed, thus, freeing up the memory used by every iteration.<\/p>\n

Applications of Recursion in R<\/h3>\n

Recursive functions are used in many efficient programming techniques like dynamic programming<\/strong> or divide and conquer algorithms<\/strong>.<\/p>\n

In dynamic programming, for both top-down as well as bottom-up approaches, recursion is vital for performance.<\/p>\n

In divide and conquer algorithms, we divide a problem into smaller sub-problems that are easier to solve. The output is then built back up to the top. Recursion has a similar process, which is why it is used to implement such algorithms.<\/p>\n

In its essence, recursion is the process of breaking down a problem into many smaller problems, these smaller problems are further broken down until the problem left is trivial. The solution is then built back up piece by piece.<\/p>\n

Now, let us look at a few examples of recursive functions.<\/p>\n

1. Factorial using Recursion in R<\/h4>\n

We can find the factorial<\/strong> of a number using recursion in R<\/a> like this:<\/p>\n

Code:<\/strong><\/p>\n

rec_fac <- function(x){\n  if(x==0 || x==1){\n    return(1)\n  } else {\n    return(x*rec_fac(x-1))\n  }\n}<\/pre>\n
Output:<\/strong><\/p>\n
\"rec_fac()<\/a><\/strong><\/p>\n
Note:<\/strong> Here, rec_fac(5)<\/code><\/strong> calls rec_fac(4)<\/code><\/strong>, which then calls rec_fac(3)<\/code><\/strong> and so on until the input argument x<\/code><\/strong>, has reached 1. The function returns 1 and is destroyed. The return value is multiplied with argument<\/strong><\/a> value and returned. This process continues until the first function call returns its output, giving us the final result.<\/p>\n
2. Sum of Natural Numbers using Recursion<\/h4>\n
Finding the sum of natural numbers is also a good use for recursive functions. In this example, we have naturals, a vector with 30 natural numbers (integers). The function sum_nat<\/code><\/strong> finds the sum of the numbers using recursion.<\/p>\n
Code:<\/strong><\/p>\n
sum_nat <- function(vec){\n  if(length(vec)<=1){\n    return(vec)\n  } else {\n    return(vec[1]+sum_nat(vec[-1]))\n  }\n}\nnaturals <- c(1:30)\nsum_nat(naturals)<\/pre>\n
Output:<\/strong><\/p>\n
\"sum<\/a><\/strong><\/p>\n
3. Sum of Series Using Recursion<\/h4>\n
Recursion in R is most useful for finding the sum of self-repeating series. In this example, we will find the sum of squares of a given series of numbers.<\/p>\n
SUM = 12<\/sup>+22<\/sup>+…+N2<\/sup><\/strong><\/p>\n
Code:<\/strong><\/p>\n
sum_series <- function(vec){\n  if(length(vec)<=1){\n    return(vec^2)\n  }else{\n    return(vec[1]^2+sum_series(vec[-1]))\n  }\n}\nseries <- c(1:10)\nsum_series(series)<\/pre>\n
Output:<\/strong><\/p>\n
\"sum<\/a><\/p>\n
4. Using Recursion to Sort a Numeric Vector<\/h4>\n
We can also use recursive functions to sort numeric vectors. In the following example, we split the given vector<\/strong> into two smaller ones containing elements larger than or smaller than the first element. These smaller vectors are then further sorted using the same function until the length of the vectors is 1 or 0. They are then arranged in order and returned.<\/p>\n
Code:<\/strong><\/p>\n
quicksort <- function(vec){\n  if(length(vec)<=1){\n    return(vec)\n  } else {\n    subject <- vec[1]\n    predicate <- vec[-1]\n    large <- predicate[predicate>subject]\n    small <- predicate[predicate<=subject]\n    large <- quicksort(large)\n    small <- quicksort(small)\n    return(c(small,subject,large))\n  }\n}\nquicksort(c(4,82,23,0,-15,16,31,-29))<\/pre>\n
Output:<\/strong><\/p>\n
\"quicksort()<\/a><\/strong><\/p>\n
Let us go through what exactly is happening in the above example.<\/p>\n
Step – 1.<\/strong> The quicksort function selects the first element of the input vector and compares it with the rest of the elements.<\/p>\n
Step – 2.<\/strong> It stores the elements larger than the subject element in the large vector and the smaller elements in the small vector.<\/p>\n
Step – 3.<\/strong> It then calls itself to sort the large and small vectors.<\/p>\n
Step – 4.<\/strong> This process repeats until the input vector has a length less than or equal to 1. In such a case, the function returns the input vector as it is.<\/p>\n
Step – 5.<\/strong> The function then arranges the vector in order as shown (small, subject, large) and returns this output.<\/p>\n
Step – 6.<\/strong> The predecessors arrange the returned output in the same order and pass it forward until the first function returns the final output.<\/p>\n
Summary<\/h2>\n
In this tutorial, we learned about recursive functions and recursion in R. We looked at a few examples and saw how the functions called themselves to solve a part of the bigger problem.<\/p>\n
Recursion is the process of breaking down problems into parts to solve them. It reduces the time and space complexity of a program and makes it more efficient.<\/p>\n
R offers many functions like –<\/p>\n