CODEWITHSUNDEEP
rfunctioncatalan
Pragyaditya Das
Pragyaditya Das

Reputation: 1696

Recursive method for Catalan numbers in R

I am trying to write a function in R that would take an input numb and output the corresponding Catalan number. For your information, the recursive formula for Catalan Numbers is, 

C_0 = 1; 
C_n = {(4n - 2)*C_(n-1)}/(n+1)

My code is as follows, 

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

When I run the function, I get,

> catalan_num_recr(3)
[1] 5

Which is correct.

AIM: However, I am trying to find Catalan's numbers for a range, I would like to find something like, catalan_num_recr(1:10).

PROBLEM: This does not work with my function, I get the following warning,

Warning messages:
1: In if (numb == 0) { :
  the condition has length > 1 and only the first element will be used

And a lot of wrong values as output, 

> catalan_num_recr(1:15)
 [1] 1.000000 2.000000 2.500000 2.800000 3.000000 3.142857 3.250000
 [8] 3.333333 3.400000 3.454545 3.500000 3.538462 3.571429 3.600000
[15] 3.625000

Can someone help me modify my function/or help me see through the problem?

Regards.

Upvotes: 0

Views: 694

Answers (5)

Elio Campitelli
Elio Campitelli

Reputation: 1476

First, the warning you're getting is telling you that in numb == 0 R will just evaluate numb[1] == 0.

While the other answers are correct, they are not very efficient because you need to compute every Catalan number multiple times. (For Catalan(15) you need to compute Catalan(14), which you've already computed)

I think this is a better version, which computes every catalan number up to the max number and then returns the ones you asked for. 

catalan <- function(numbs) {
   cat <- vector("numeric", length(max(numbs)) + 1)
   for (i in 0:max(numbs)) {
      if (i == 0) {
         cat[i+1] <- 1
      } else {
         cat[i+1] <- ((4*i - 2)*cat[i])/(i + 1)
      }
   }
   cat[numbs + 1]
}

> catalan(1:15)
 [1]       1       2       5      14      42     132     429
 [8]    1430    4862   16796   58786  208012  742900 2674440
[15] 9694845

Here's a small benchmark where catrvect = Vectorize(catalan_num_recr)

microbenchmark::microbenchmark(catalan(1:100), catvect(1:100))
Unit: microseconds
           expr      min        lq      mean    median       uq
 catalan(1:100)   86.515   98.7565  127.3139  122.7665  141.423
 catvect(1:100) 4764.728 4947.3070 5661.0624 5124.3385 5647.238
       max neval
   276.825   100
 11009.428   100

Of course, the function now is not recursive.

Upvotes: 1

rg255
rg255

Reputation: 4169

You could use sapply (or lapply) on your vector of numbers

sapply(c(0:15), catalan_num_recr)

And just putting the output in a dataframe so you can check the numbers 

data.frame("n" = c(0:5), "cnr" = sapply(c(0:5), catalan_num_recr))

  n cnr
1 0   1
2 1   1
3 2   2
4 3   5
5 4  14
6 5  42

Upvotes: 1

James
James

Reputation: 66844

Use Vectorize which takes a function and returns a new function which is essentially a wrapper to your function that accepts vectorised input. The computation is actually performed repeatedly by mapply so it won't be as fast as writing a function that is vectorised by hand.

Vectorize(catalan_num_recr)(1:15)
 [1]       1       2       5      14      42     132     429    1430    4862
[10]   16796   58786  208012  742900 2674440 9694845

Upvotes: 2

Adam Birenbaum
Adam Birenbaum

Reputation: 950

You just need to use a vectorized function like sapply from the apply family.

sapply(1:10,catalan_num_recr,USE.NAMES = F)

Upvotes: 1

Calum You
Calum You

Reputation: 15072

Your function does not currently accept a vector input. This may be a little confusing because many functions such as the maths operators are vectorised by default. You need to apply the function to each element of the vector with a map or apply function. This is effectively a fast loop, and the purrr package has the advantage of a consistent syntax and being type stable.

catalan_num_recr <- function(numb){
  if (numb == 0){
    return(1)
  }
  else
    return(((4*numb-2)*catalan_num_recr(numb-1))/(numb+1))
}

purrr::map_dbl(1:15, catalan_num_recr)
#>  [1]       1       2       5      14      42     132     429    1430
#>  [9]    4862   16796   58786  208012  742900 2674440 9694845

Created on 2018-05-21 by the reprex package (v0.2.0).

Upvotes: 1

Related Questions