Fibonacci

The Fibonacci series is a series of numbers where fib(n) is the sum of fib(n-2) and fib(n-1).
When you find it in an interview question it is usually an opportunity to talk about recursion.

Recursion has these requirements.
    It must have a base state.
    It must change its state.
    It must call itself to move towards its base state.

The base state for fibonacci is 1. It helps to remember that this calculation is meant to plot
a line. A line length of zero is not really meaningful; thus, fib(0) is simply 0. Fib(1) doesn’t
have enough operands to calculate using fib(n) = (fib(n-2) + fib(n-1)) so we can take it at
face value too. At fib(2) we can start working: fib(2) = fib(2-2) + fib(2-1). You can see from
this that we will need to make sure we have return values for fib(0) and fib(1) to calculate
fib(2) correctly.

fib(0) = 0

fib(1) = 1

fib(2) 0 + 1 = 1

fib(3) 1 + 1 = 2

fib(4) 1 + 2 = 3

fib(5) 2 + 3 = 5

Use caution when you code this up. It doesn’t take long to get into really big numbers. You

shouldn’t use values of N higher than 35 or so without bringing a sandwich. Stay tuned for
test results on what happens with really big numbers. Theoretically the program will fill the
available physical ram, then consume paged ram (ram that is written to hard disk) until it
finds the answer or hitting the wall on how much RAM the OS is willing to give up. I am
guessing that the kernel will panic before the heat death of the universe with really, really
big numbers, but I am not going to bet the farm on it. I tried a value of 200 for N and got
bored before getting anything other than a pegged CPU.

Here is my Fibonacci function:

def fib(num):

   If num <= 1:

       return num

   else:

       return (fib(num-1) + fib(num-2))