# How do I create a recursive tree plot for the Fibonacci sequence?

I would like to create a plot that shows the recursive tree for the nth number of the fibonacci sequence, as the one below.

http://faculty.ycp.edu/~dhovemey/fall2005/cs102/lecture/fib5.png

Ideally, I want to call a function that changes the tree for a given nth element. I thought about doing this recursively, and I also tried using Tree Graph, but I can't seem to get it to work! The main problem is how to differentiate the nodes, but still label them the same number. For example, I will end up having many '1's, but I cannot name each of these '1.'

• Post the code you have written. May 31, 2016 at 14:10

Since each vertex has to be named uniquely, for example with its path through the tree, it is simply a case of using the end of the path in a custom VertexRenderingFunction.

One way of generating the edge list:

f[___, 0] = {};
f[___, 1] = {};
f[m___, n_] := {{m, n} -> {m, n, n - 1}, {m, n} -> {m, n, n - 2},
f[m, n, n - 1], f[m, n, n - 2]}


Then

g = f[5] // Flatten


{{5} -> {5, 4}, {5} -> {5, 3}, {5, 4} -> {5, 4, 3}, {5, 4} -> {5, 4,
2}, {5, 4, 3} -> {5, 4, 3, 2}, {5, 4, 3} -> {5, 4, 3, 1}, {5, 4, 3, 2} -> {5, 4, 3, 2, 1}, {5, 4, 3, 2} -> {5, 4, 3, 2, 0}, {5, 4, 2} -> {5, 4, 2, 1}, {5, 4, 2} -> {5, 4, 2, 0}, {5, 3} -> {5, 3,
2}, {5, 3} -> {5, 3, 1}, {5, 3, 2} -> {5, 3, 2, 1}, {5, 3, 2} -> {5, 3, 2, 0}}

An example plot:

TreePlot[g, Top, {5},
VertexRenderingFunction -> (Inset[Row[{"fib(", Last[#2], ")"}], #1,
Background -> White] &)]


• Thats a very interesting way to look at this question. Thanks for the help. However, I am trying to use some sort of Manipulate where the user can visualize the recursive tree for the nth element. How would you propose doing this given the above vertex rendering function? Jun 1, 2016 at 4:53
• Why not simply combine the RHS of the definition of g with the TreePlot expression and change both instances of 5 to your Manipulate variable? Jun 1, 2016 at 7:15

This is a way using RelationGraph (essentially implementing MikeLimaOscar's approach) but not as nicely or efficiently.

fun[x__] :=
If[Last[x] <=
1, {}, {{x, Append[x, Last@x - 1]}, {x, Append[x, Last@x - 2]}}]
lab[n_] := "fib[" <> ToString[Last@n] <> "]";
rec[n_] :=
Module[{gd =
Catenate@NestList[Last /@ Flatten[fun /@ #, 1] &, {{n}}, n - 1],
r},
r = RelationGraph[
SubsetQ[#2, #1] && #1[[-1]] - #2[[-1]] > 0 &&
Length[#2] - Length[#1] == 1 &, gd];
TreePlot[Rule @@@ EdgeList[r],
VertexRenderingFunction -> (Text[
Framed[Style[lab[#2], Blue], Background -> White], #1] &)]
]


Examples for 2 to 6. It gets unwieldy (as well as too crowded) for n>10: