CSCE 222 Lecture 1

« previous | Wednesday, January 19, 2010 | next »

Introduction

We'll be using Ruby!!!!

… with a lot of math symbols

Fibonacci Numbers

$f_{n}={\begin{cases}0&n=0\\1&n=1\\f_{n-1}+f_{n-2}&n>1\end{cases}}$

def fib(n)
  return n if n <= 1
  fib(n-1) + fib(n-2)
end

11.times { |i| puts fib(i) }

how long will fib(40) take? (A long time)

Recursion and Benchmarking

• fib(n) calls f(n-1) and f(n-2)
  • fib(n-1) calls fib(n-2) and fib(n-3)
  • fib(n-2) calls fib(n-3) and fib(n-4)

f(n-3), for example, is called multiple times for duplication; time needed grows exponentially.

Exponential ratio eventually converges to the golden ratio:

${\frac {Time\left(f_{n}\right)}{Time\left(f_{n-1}\right)}}\approx {\frac {1+{\sqrt {5}}}{2}}\approx 1.618033988$

A better function

def fib(n)
  return n if n <= 1
  @res ||= fib(n-1) + fib(n-2)
end

Dramatic speed enhancement

Even better function

@res = []
def fib(n)
  return n if n <= 1
  @res[n] ||= fib(n-1) + fib(n-2)
end