# Iterative and recursive approach to generate Fibonacci sequence

I'm new to use Mathematica and using this demo project to understand Mathematic demo example. I modified example code to only plot the runtime of recursive version of Fibonacci sequence runtime:

Clear[recFib];
recFib[n_] := recFib[n] = recFib[n - 1] + recFib[n - 2]
recFib[0] = 0; recFib[1] = 1;

timeComplex[n_] :=
Plot[{recFib[x], x}, {x, 0, n}, PlotRange -> {{0, 10}, {0, 100}},
PlotStyle -> {Thickness[0.01], Thickness[0.01]},
PlotLabel ->  "time complexity", AxesLabel -> {n, time},
PlotLegends ->
Placed[LineLegend[{"recursive"},
LegendFunction -> "Frame",
LegendLayout -> "Column"], {{0.25, 0.5}, {0.25, 0.1}}],
ImageSize -> {200, 200}]

Manipulate[
GraphicsGrid[{{timeComplex[n]}}, Alignment -> {Center, Top},
Frame -> All], {{n, 2, "Fibonacci number"}, 2, 10, 1,
Appearance -> "Labeled"}, ControlPlacement -> Top,
SaveDefinitions -> True]


However, the output graph still contains iterative runtime of Fibonacci. Could someone teach me where it comes from? Thanks.

• Do you mean that it only contains a straight line? Try maybe DiscretePlot instead of Plot in your definition of timeComplex. I think Plot would not play well with recFib which is only properly defined for integer values of n. Feb 16, 2021 at 5:39
• Yes, that's exactly my problem. Thank you very much.
– Dan
Feb 16, 2021 at 16:21

Because by default when you use Plot, it uses very small numbers to give you a smooth plot and in this case, this is not what you want. Because if you use step values less than $$1$$, like recFib[3.5], the program will fall short in recursion without any result.

Solution is to specify plot step as 1, since Plot doesn't have a step option, you can use DiscretePlot as shown below ( $$...$$ is the options you have specified):

timeComplex[n_] :=  DiscretePlot[{recFib[x], x}, {x, 0, n, 1}, Joined -> True, Filling -> None, ...]


Also for the AxesLabel you use symbols, not strings, so I change time to "time" and n to "n".

Full code:

recFib[n_] := recFib[n] = recFib[n - 1] + recFib[n - 2]
recFib[0] = 0; recFib[1] = 1;

timeComplex[n_] :=
DiscretePlot[{recFib[x], x}, {x, 0, n, 1}, Joined -> True,
Filling -> None, PlotRange -> {{0, 10}, {0, 100}},
PlotStyle -> {Thickness[0.01], Thickness[0.01]},
PlotLabel -> "time complexity", AxesLabel -> {"n", "time"},
PlotLegends ->
Placed[LineLegend[{"recursive"}, LegendFunction -> "Frame",
LegendLayout -> "Column"], {{0.25, 0.5}, {0.25, 0.1}}],
ImageSize -> {200, 200}]

Manipulate[
GraphicsGrid[{{timeComplex[n]}}, Alignment -> {Center, Top},
Frame -> All], {{n, 2, "Fibonacci number"}, 2, 10, 1,
Appearance -> "Labeled"}, ControlPlacement -> Top,
SaveDefinitions -> True]

• Now I get it. Thank you very much!
– Dan
Feb 16, 2021 at 16:21