Fibonacci Sequence

A pitch presentation

JB

What is the Fibonacci Sequence?

The Fibonacci Sequence is a sequence of integer numbers that follow these rules:

  1. The first two numbers in the sequence are equal to 1: F(1) = 1, F(2) = 1
    It is also possible to add F(0) = 0, or even extend to negativ numbers, but for the app we started with 1.
  2. For n > 2 the corresponding Fibonacci number is the sum of the two previous ones:
    F(n) = F(n-1) + F(n-2)

Examples:

  • F(3) = F(2) + F(1) = 1 + 1 = 2
  • F(4) = 2 + 1 = 3
  • The first 10 Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Features of the Application

  • The shiny application takes a whole positive number n as input and calculates the Fibonacci number F(n).
  • If the input value is not a whole positive number the application will throw an error and stop.
  • The application uses an iterative algorithm since this is most intuitive.
  • Documentation for users is included in the app on the tab named "Documentation".

How Does the Algorithm Work?

As mentioned before we use an iterative algorithm which means it starts with F(1) = 1 and F(2) = 1 and then calculates subsequently every F(i) for 2 < i <= n by remembering the last two results F(i-1) and F(i-2) and adding those up to obtain the next number in the sequence. This result is stored again together with the previous one to calculate the next number and so forth.

Here is a chunk of code from the application for an example of n = 10:

n <- 10
prev <- 1; nex <- 1
for (i in 2:(n-1)){
  res <- prev + nex
  prev <- nex
  nex <- res
}  
res

## [1] 55

Alternative Algorithms

There are different approaches to calculate Fibonacci numbers. Besides the iterative algorithm used in the shiny app, we want to discuss a recursive algorithm. There is also an analytic approach using the golden ratio, which we will not discuss here.

Recursive Algorithm

This needs only very few lines of code. It looks like this (no error-handling included):

F <- function(n) {
  if (n < 3) res <- 1
  else res <- F(n-2) + F(n-1)
  res
}

While this needs fewer lines of code than the iterative approach, it does take significantly longer to compute due to a lot of recursive function calls. For example for the call F(5) this algorithm will first call F(4) and F(3), in another step F(3), F(2), F(2), F(1) and finally another time F(2) and F(1). While this is not a problem yet for n = 5, it is easy to see that it will take a lot more time when n gets bigger.