- #1
dobry_den
- 115
- 0
In chapter five of Douglas Hofstadter's book Goedel, Escher, Bach, the author poses a question about recursively-defined trees:
I've been trying to solve it today, and the only solution I came up with is:
[...]suppose you flip Diagram G around as if in a mirror, and label the nodes of the new tree so they increase from left to right. Can you find a recursive algebraic definition for this "flip-tree"?
I've been trying to solve it today, and the only solution I came up with is:
G(n) = (n+1) - G(G(n-1)+1) for n>4
G(O) = 0, G(1) = 1, G(2) = 2, G(3) = 3, G(4) = 3 (hope i remember it well),
which is apparently not as elegant as the original definition. Has anyone of you come up with a better solution? Or is there any general method (procedure) how to transform recursive algebraic definition of trees into recursive algebraic definitions of "flip-trees"?G(O) = 0, G(1) = 1, G(2) = 2, G(3) = 3, G(4) = 3 (hope i remember it well),