not using for loop in R for recursion?

Question

I wonder how I can code recursion not using a for loop for a vector? Will it be more efficient?

My for loop code:

fib <- function(n){

  if (n==2){
    return c(1,1)
  }
  if (n==1){
    return c(1)
  }

  v=c(1,1)
  for (i in 3:n ) {
    v=c(v,v[i-1]+v[i-2])
  }  

  return(v)

}

I look at a post and it says it is not efficient to append to a vector in R as the whole vector is re-created?

First off, your base cases are not valid r syntax. You may want `rep(1,2)` and `1` respectively for those (i.e. the brackets are not valid). — devmacrile, Oct 02 '15 at 17:32
Hi Roland. Thanks for the reply. I want to series not the sum — Mookayama, Oct 02 '15 at 19:05

score 0 · Answer 1 · answered Oct 02 '15 at 19:43

I know this does not answer your question about generating the Fibonacci series without a for loop but a fast solution could be to use Rcpp. Code recursion without growing the resulting vector becomes messy.

#include <Rcpp.h>
using namespace Rcpp;

// [[Rcpp::export]]                                                                                               
NumericVector fib(int n) {

  NumericVector res(n);

  if (n==0)
    return(res);

  res(0) = 1;

  if (n>1) {
    res(1) = 1;

    for (int i=2; i < n ; i++) {
      res(i) = res(i-1) +   res(i-2);
    }
  }
  return(res);
}

You can compile the code using

library(Rcpp)
sourceCpp(file="fib.cpp")

# Test
fib(5)
fib(100)

not using for loop in R for recursion?

1 Answers1