2
$\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.'

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Post the code you have written. $\endgroup$
    – Sektor
    Commented May 31, 2016 at 14:10

2 Answers 2

Reset to default
6
$\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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 1, 2016 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
    Commented Jun 1, 2016 at 7:15
2
$\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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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