my-reverse
, since there's a builtin function
reverse
already.
(define (my-reverse L) (if (null? L) '() (append (my-reverse (cdr L)) (list (car L)))))If you go ahead and run this on some short lists, it works just fine. What about larger lists? With the help of the
bl function
(define (bl n) (if (= n 0) '() (cons n (bl (- n 1)))))
for creating some large lists, we can see that it's not too
fast.
> (define L (bl 10000))
> (time (car (my-reverse L)))
cpu time: 25730 real time: 53807 gc time: 12540
1
>
The reasons are two-fold: the function is not tail-recursive,
and the append
call needs to do some copying.
In fact, tailrecursive-ness only affects the hidden
constant, wheras the copying append
needs to do
leads, in this example, to an n^2 running time.
Still, let's try and formulate the thing tailrecursively
anyway.
(define (my-reverse-tr L c)
(if (null? L)
c
(my-reverse-tr (cdr L) (cons (car L) c))))
Notice that adding this extra argument c
to pass
along partial results from one function to the next resulted in a
natural formulation using cons
instead of
append
. So we solved both problems at once!
> (time (car (my-reverse-tr L '())))
cpu time: 30 real time: 34 gc time: 0
1
The moral of the story is ... that this idea of adding
extra parameters to pass along partial results can be
used to to increase efficiency in ways that have nothing to do
with tail-recursion! In fact, in many cases the function you
want at the user level is just a wrapper that calls a
recursive function with many more paramters; parameters that
pass along extra information that makes the function easier to
write.