A curious question:
Which is more efficient in rebuilding a (small) list using recursion.
A.
rebuild the list using tail recursion with a helper function
cons(ing) each of the items on to a newlist and then reversing the list
when done.
B.
Using augmentative recursion and rebuilding the list once the entire list
has been processed.
I know A is obviosly faster for huge lists. But what about small list
(say length of 2 - 4). Will reversing the list take up more resources
than just rebuilding the list using the interpreters stack
(augmentative).
I know this is probably a dumb question... but im not exactly a bright
lisp programmer... thanks
Adam Gent wrote:
> A curious question:
>
> Which is more efficient in rebuilding a (small) list using recursion.
>
> A.
> rebuild the list using tail recursion with a helper function
> cons(ing) each of the items on to a newlist and then reversing the list
> when done.
>
> B.
> Using augmentative recursion and rebuilding the list once the entire list
> has been processed.
>
> I know A is obviosly faster for huge lists. But what about small list
> (say length of 2 - 4). Will reversing the list take up more resources
> than just rebuilding the list using the interpreters stack
> (augmentative).
>
> I know this is probably a dumb question... but im not exactly a bright
> lisp programmer... thanks
The best solution is maybe to do not use recursion at all. Common Lisp's
LOOP facility has rich support for iterating over and collecting into a
list.
(loop for i from 1 to 5
collect (* i i))
==> (1 4 9 16 25)
The nice thing is that LOOP constructs the list in this order without
the need for a REVERSE.
ciao,
Jochen