1
$\begingroup$

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.'

$\endgroup$
  • 1
    $\begingroup$ Post the code you have written. $\endgroup$ – Sektor May 31 '16 at 14:10
5
$\begingroup$

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] &)]

Fibonacci tree plot

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – rajann Jun 1 '16 at 4:53
  • $\begingroup$ 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? $\endgroup$ – MikeLimaOscar Jun 1 '16 at 7:15
1
$\begingroup$

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:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.