# Using trace for Fibonacci

The Fibonacci function I have constructed is:

f[n_] := f[n] = f[n - 1] + f[n - 2]

f[0] = 0; f[1] = 1;

with the first 20 values of the Fibonacci

Array[f, 20]

I would like to compute the 5th value of the Fibonacci but with the aid of the Trace function. However, I dod not understand the role of this function. No proper/ in depth explanation has been provided by Mathematica.

Any help is appreciated.

Edit:

You just apply Trace to the expression you want to see.

Clear[f]
f[n_] := f[n] = f[n - 1] + f[n - 2]
f[0] = 0; f[1] = 1;
Trace[f[3]]


What may be confusing you is the memoization. The code stores the values in a table the first time they are computed. Thus, if you ask for

Trace[f[3]]
{f[3],2}


a second time, you only get a terse response. This is why I added the Clear at the front.

• Hi bill, why is there a hold in the output? Mar 26, 2017 at 13:50
• I see no Hold... try running with a new kernel since that may be due to old definitions. Mar 26, 2017 at 13:51
• I have edited the OP with a shot of the "hold" Mar 26, 2017 at 13:54
• Copy-paste my code (and change the 3 to a 5 if you wish). There is no Hold. You need to restart the kernel. You have some lingering definitions. Mar 26, 2017 at 13:57
• Is there a way to modify my above code to utilise dynamic programming to compute the 200th value of the Fibonacci sequence? Mar 26, 2017 at 14:05

This is an extended comment rather than an answer

ClearAll[f];


Using RSolve

RSolve[
{f[n] == f[n - 1] + f[n - 2], f[0] == 0, f[1] == 1},
f[n], n]

(*  {{f[n] -> Fibonacci[n]}}  *)


The Fibonacci function is

Fibonacci[n] // FunctionExpand

(*  ((1/2 (1 + Sqrt[5]))^n - (2/(1 + Sqrt[5]))^n Cos[n π])/Sqrt[5]  *)


Looking at the expression for GoldenRatio

GoldenRatio // FunctionExpand

(*  1/2 (1 + Sqrt[5])  *)


Then

Fibonacci[n] == (GoldenRatio^n - GoldenRatio^-n Cos[n Pi])/Sqrt[5]
// FunctionExpand

(*  True  *)


The recursive definition of the sequence for both positive and negative n is

f[0] = 0;
f[1] = 1;
f[n_?Positive] := f[n] = f[n - 1] + f[n - 2];
f[n_?Negative] := f[n] = f[n + 2] - f[n + 1];


Demonstrating that the sequence lies on the Plot of the Fibonacci function

Plot[Fibonacci[n], {n, -5.2, 5.2},
Epilog -> {Red, AbsolutePointSize[6],
Point[{#, f[#]} & /@ Range[-5, 5]]}]