# [plt-scheme] Tree recursion

 From: Robby Findler (robby at cs.uchicago.edu) Date: Tue Jan 22 22:29:20 EST 2008 Previous message: [plt-scheme] Tree recursion Next message: [plt-scheme] Tree recursion Messages sorted by: [date] [thread] [subject] [author]

```You can try thinking about it algebraically. Each equality below
corresponds to using the tree-copy just one time (well, except once
where I took two steps at once).

Robby

(define tree-copy
(lambda (tr)
(if (not (pair? tr))
tr
(cons (tree-copy (cdr tr))
(tree-copy (car tr))))))

(tree-copy '((a . b) . c))
=
(cons (tree-copy 'c)
(tree-copy '(a . b)))
=
(cons 'c
(tree-copy '(a . b)))
=
(cons 'c
(cons (tree-copy 'b)
(tree-copy 'a)))
=
(cons 'c
(cons 'b
'a))
aka
'(c . (b . a))
aka
'(c b . a)

On Jan 22, 2008 9:11 PM, Grant Rettke <grettke at acm.org> wrote:
> Hi folks,
>
> I am working on problem 2.8.1 in TSPL:
> http://www.scheme.com/tspl3/start.html#./start:h8
>
> I am having a tough time visualizing this. I tried tracing it and
> drawing it out on paper. What makes me think I don't understand this
> well enough is that the answer is not obvious to me.
>
> At risk of this being a dumb question, is there a good way to go about
> understanding/visualizing this kind of recursion other than what I am