**Challenge:**

Write a function in R that prints the n^{th} 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:

- One by writing the function using for loop.
- 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:

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*.