[plt-scheme] Tree recursion

From: Robby Findler (robby at cs.uchicago.edu)
Date: Tue Jan 22 22:29:20 EST 2008

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
> already doing?
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>


Posted on the users mailing list.