From SICP
Exercise 2.28: Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,
(define x (list (list 1 2) (list 3 4))) (fringe x) (1 2 3 4) (fringe (list x x)) (1 2 3 4 1 2 3 4)
After writing this code, I found out that implementing this in an iterative way is easier and more straight forward. But I ended up implementing this in a more complicated way. I'd like to think this is a recursive process. The argument "remaining" is not an accumulator. It stores all remaining items that are not yet consed into the new list.
Please review my code.
(define (fringe tree)
(define (aux lst remaining)
(cond
((null? lst)
(if (null? remaining)
'()
(aux remaining '())))
((pair? (car lst)) (aux (car lst) (aux (cdr lst) remaining)))
(else (cons (car lst) (aux (cdr lst) remaining)))))
(aux tree '()))
- How does it compare to the iterative version I linked to above?
- What is the order of growth of my function? Is it O(N)?
- How can it be faster?
- If I used append rather than cons, would it slow my function a lot?
- How can I improve this code?