Computing Fibonacci Numbers Recursively

fib[0]=0
fib[1]=1
fib[n_]:=fib[n-1]+fib[n-2]

Try it out:

{fib[3],fib[4],fib[5]}

Table[fib[n],{n,0,10}]

Map[fib,Range[0,10]]

fib/@Range[0,10]

How long does it take to compute Fibonacci numbers this way?

Timing[fib[10]]

Timing[fib[20]]

Timing[fib[30]]

Write a function to extract the runtime from the Timing function:

myFibTime[n_]:=Timing[fib[n]][[1]]

Double square brackets denote the Part operator, which gets a value from a list.

myFibTime[30]

Make a list of runtimes for computing Fibonacci numbers:

fibTimes=myFibTime/@Range[30]

ListPlot[fibTimes]

Could it be exponential?

Iterative Approach

goal : computeFib[n] returns the nth Fibonacci number (Subscript[F, n])

computeFib[n_]:=Module[{a=0,b=1,next},
Do[next=a+b;  (* compute the next Fibonacci number *)
a=b; (* shift b to a *)
b=next (* shift next to b *)
,n-1]; (* or {k,2,n} *)
b (* return value *)
]

Try it out :

computeFib/@Range[10]

computeFib[2000]

Timing[computeFib[2000]]

Ratios of Consecutive Fibonacci Numbers

Compute ((Subscript[F, n])/(Subscript[F, n-1])) for various values of n. What do you observe?

N[computeFib[20]/computeFib[19]]

Table[N[computeFib[n]/computeFib[n-1],20],{n,1,20}]

Table[N[computeFib[n-1]/computeFib[n],20],{n,1,20}]

Start with a big list of Fibonacci numbers:

fibs=computeFib/@Range[100]

numerators=fibs[[2;;100]]; (* get indexes 2 through 100 from the list *)
denominators = fibs[[1;;99]]; (* get indexes 1 through 99 *)
ratios=numerators/denominators;
N[ratios,20]