Write a Function that Returns the nth Fibonacci Number in R

By /

Challenge:

Write a function in R that prints the nth Fibonacci number.

Reminder: the Fibonacci sequence is: 1, 1, 2, 3, 5, 8, …

So, the first Fibonacci number is 1, the second is also 1, and then each subsequent number is the sum of the previous 2 in the sequence.

Solution:

In this article, I will present 2 solutions:

  1. One by writing the function using for loop.
  2. And the other by writing the function using recursion.

Then, we will compare the runtime of the 2 solutions, and provide a trick to speed up the slower one.

1. Writing a Fibonacci function using a for loop

# Fibonacci function using a for loop
loopFib = function(n) {
  
  # start the sequence with: 1, 1
  fibSeq = c(1, 1)
  
  # fill the rest of the sequence for n > 2
  if (n > 2) {
    for (i in 3:n) {
      # each number is the sum of the 2 preceding ones
      fibSeq[i] = fibSeq[i - 1] + fibSeq[i - 2]
    }
  }
  
  # return the nth number in the sequence
  fibSeq[n]
}

Testing the function loopFib:

loopFib(1) # outputs: 1
loopFib(2) # outputs: 1
loopFib(3) # outputs: 2
loopFib(30) # outputs: 832040

# print the first 10 numbers of the Fibonacci sequence
n = 1:10

# making the function loopFib accept vector inputs
# this is simpler than entering each input separately
loopFib = Vectorize(loopFib)

loopFib(n) # outputs: 1  1  2  3  5  8 13 21 34 55

2. Writing a Fibonacci function using recursion

# Fibonacci function using recursion
recursiveFib = function(n) {
  
  # when n is 1 or 2, return 1
  if (n == 1 || n == 2) {1}
  
  # else, return the sum of the previous 2 numbers
  # by calling the current function on n-1 and n-2
  else {
    recursiveFib(n - 1) + recursiveFib(n - 2)
  }
}

Testing the function recursiveFib:

recursiveFib(1) # outputs: 1
recursiveFib(2) # outputs: 1
recursiveFib(3) # outputs: 2
recursiveFib(30) # outputs: 832040

# print the first 10 numbers of the Fibonacci sequence
n = 1:10

# making the function recursiveFib accept vector inputs
# this is simpler than entering each input separately
recursiveFib = Vectorize(recursiveFib)

recursiveFib(n) # outputs: 1  1  2  3  5  8 13 21 34 55

Notice that calling recursiveFib(30) took some time to run.

So, let’s compare the speed of the 2 function: recursiveFib and loopFib.

Comparing the speed of the recursive function and the loop function

We will compare the runtime in seconds of the 2 algorithms:

# runtime of loopFib
t1 = Sys.time() # start timer
loopFib(30)
t2 = Sys.time() # stop timer

print(paste('looping takes:', round(t2 - t1, 4), 'seconds'))
# outputs: "looping takes: 0.009 seconds"

# runtime of recursiveFib
t1 = Sys.time() # start timer
recursiveFib(30)
t2 = Sys.time() # stop timer

print(paste('recursion takes:', round(t2 - t1, 4), 'seconds'))
# outputs: "recursion takes: 0.7789 seconds"

Why the recursive function is much slower?

Let’s look at the example of how the recursive function works when n = 30:

How the recursive Fibonacci algorithm works

Looking at the picture above, we see that recursiveFib(30) was called once, but recursiveFib(28) and recursiveFib(27) were called more than once. So, the function is expected to be slow since it is computing the same numbers multiple times.

Speeding up the recursive function

So our problem is that recursiveFib gets called more than once with the same input n.

An easy fix is to create some sort of memory (technically a vector, for example) that stores the computed results, and then these will be returned when needed — a process called memoization.

# creating the memo, that contains for now
# only the results of the first 2 Fibonacci numbers
memo = c(1, 1)
  
fastFib = function(n) {

  # check if the result is already computed
  if (!is.na(memo[n])) {
    return (memo[n])
  }

  # else, compute the result and store it in the memo
  else {
    ans = fastFib(n-1) + fastFib(n-2)
    memo[n] <<- ans # see below for details on <<- operator
    return (ans)
  }
}

Note that I used the <<- operator inside the function to change the value of the variable memo which is defined outside of the function.

To understand why, we need to understand the scoping rules in R.

Consider the following code:

# scoping rules
x = 1

f = function() {
  x = 2
  print(paste('x inside f is', x))
}

f()
print(paste('x outside of f is', x))

# this code prints:
# "x inside f is 2"
# "x outside of f is 1"

So, x is still 1 once the function stops running.

To change x in the “global environment” (i.e. outside of the function) from within the function, we use the double arrow operator (<<-):

x = 1

f = function() {
  x <<- 2
  print(paste('x inside f is', x))
}

f()
print(paste('x outside of f is', x))

# this code prints:
# "x inside f is 2"
# "x outside of f is 2"

Comparing the speed of recursiveFib with memoization fastFib

Now we will compare how many times the ordinary recursive function recursiveFib gets called (for n = 30) with the recursive function with memoization fastFib.

First, we start with the ordinary recursive function:

ncalls = 0

recursiveFib = function(n) {
  ncalls <<- ncalls + 1 # note the double arrow assignment discussed above
  
  if (n == 1 || n == 2) {1}
  else {
    recursiveFib(n - 1) + recursiveFib(n - 2)
  }
}

recursiveFib(30)
ncalls

# ncalls is 1664079

Now, let compare that to the recursive function with memoization:

memo = c(1, 1)
ncalls = 0

fastFib = function(n) {
  ncalls <<- ncalls + 1
  if (!is.na(memo[n])) {
    return (memo[n])
  }
  else {
    ans = fastFib(n-1) + fastFib(n-2)
    memo[n] <<- ans
    return (ans)
  }
}

fastFib(30)
ncalls

# ncalls is 57

In conclusion, fastFib is ~29,000 times faster (1,664,079 / 57 = 29194.37) than recursiveFib.

Further reading