Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Plotting a recursion tree

• To: mathgroup at smc.vnet.net
• Subject: [mg108010] Plotting a recursion tree
• From: metobillc <metobillc at gmail.com>
• Date: Fri, 5 Mar 2010 04:32:28 -0500 (EST)

Hello,

  I'd like to be able to plot recursion trees, e.g. if I have a
recurrence relation T(n) = 4T(n/2) + c n^2, T(1) = d (for integer n),
and I want to plot T(8), I'd like to see a tree with 64 c at the head,
4 children with 16 c, 16 grandchildren with 4 c, 64 great granchildren
with d (they are the leaves of the tree).  The best I've come up with
so far is:

mylist[a_Integer /; a > 0, b_Integer /; b > 0, x_, depth_Integer /;
depth > 0] := NestList[Table[#/b, {a}] &, x, depth]

mylist[4,2,x,3] yields
{x,
{x/2, x/2, x/2, x/ 2},
{{x/4, x/4, x/4, x/4}, {x/4, x/4, x/4, x/4}, {x/4, x/4, x/4, x/4}, {x/
4, x/4, x/4, x/4}}, {{{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}},
 {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
8, x/8, x/8, x/8}},
 {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
8, x/8, x/8, x/8}},
 {{x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/8, x/8, x/8, x/8}, {x/
8, x/8, x/8, x/8}}}}

How can I get a separate case for the leaves, and then plot a list
like this in tree form?  TreeForm[mylist[4,2,x,3]] has a bunch of
nodes called "List" and "Times", and is not symmetric -- I just want
the elements of the list.

Thanks,

Bill Campbell
Naval Research Laboratory
Monterey, CA

• Follow-Ups:
  • Re: Plotting a recursion tree
    • From: Leonid Shifrin <lshifr@gmail.com>