Fibonacci Sequence¶

The “Fibonacci Sequence” is a sequence of numbers where every number is the sum of the two numbers preceding it. The sequence begins with the numbers 0 and 1. So the beginning of the sequence goes 0, 1, 1, 2, 3, 5, 8, 21, etc.. This appears in nature a lot, such as in tree branching, the arrangement of leaves on a stem, and Spongebob’s house.

I’m not kidding.

Don’t worry, they fixed it later.

The sequence can come up in math and even programming sometimes, but here we’re using it as a good example of “recursion” and something that can be optimized further.

“Recursion”, in programming, just means that there’s a function that calls itself. Here, we give the fib function (short for fibonacci) the number 32, meaning get the 32nd fibonacci number. To get that value, we add the 30th and 31st fibonacci numbers, so we call fib again on those, which means getting the 29th and 28th numbers, and so on, until we get the starting numbers 0 or 1, in which case we return them.

This isn’t that efficient though. After this, we can optimize it with “memoization”, as seen on this page: Fibonacci Sequence (Memoization).

#include <iostream>
using namespace std;

long fib(long n){
  if(n == 0 || n == 1)
    return n;
  return fib(n-1) + fib(n-2);
}

int main(){
  cout << fib(32) << endl;
  return 0;
}

class Program{
  static long fib(long n){
    if(n == 0 || n == 1)
      return n;
    return fib(n-1) + fib(n-2);
  }
  static void Main(string[] args){
    System.Console.WriteLine(fib(32));
  }
}

public class fibonacci{
  public static long fib(long n){
    if(n == 0 || n == 1)
      return n;
    return fib(n-1) + fib(n-2);
  }
  public static void main(String[] args) {
    System.out.println(fib(32));
  }
}

function fib(n) {
  if(n === 0 || n === 1)
    return n;
  return fib(n-1) + fib(n-2);
}
console.log(fib(32));

def fib(n):
  if n == 0 or n == 1:
    return n
  return fib(n-1) + fib(n-2)

print(fib(32))

func fib(_ n: Int) -> Int {
  if n == 0 || n == 1 {
    return n
  }
  return fib(n-1) + fib(n-2)
}
print(fib(32))

Notes¶

long here is a number type, just like int, but it can store larger numbers.

Because javascript is loosely typed (no types such as int are specified), be careful not to pass in a decimal number because this relies on equality comparisons, which is very not recommended for floating-point types. To quote Wikipedia,

“The use of the equality test (if (x==y) …) requires care when dealing with floating-point numbers. Even simple expressions like 0.6/0.2-3==0 will, on most computers, fail to be true (in IEEE 754 double precision, for example, 0.6/0.2-3 is approximately equal to -4.44089209850063e-16). Consequently, such tests are sometimes replaced with “fuzzy” comparisons (if (abs(x-y) < epsilon) …, where epsilon is sufficiently small and tailored to the application, such as 1.0E−13).”

Because Python is loosely typed (no types such as int are specified), be careful not to pass in a decimal number because this relies on equality comparisons, which is very not recommended for floating-point types. To quote Wikipedia,

“The use of the equality test (if (x==y) …) requires care when dealing with floating-point numbers. Even simple expressions like 0.6/0.2-3==0 will, on most computers, fail to be true (in IEEE 754 double precision, for example, 0.6/0.2-3 is approximately equal to -4.44089209850063e-16). Consequently, such tests are sometimes replaced with “fuzzy” comparisons (if (abs(x-y) < epsilon) …, where epsilon is sufficiently small and tailored to the application, such as 1.0E−13).”

Swift uses the largest Int type it can by default (32 bit, 64 bit, etc.), so we can just use Int and it should work for large numbers.