[racket] Question about tail recursion

On Fri, Aug 8, 2014 at 12:17 PM, Matthias Felleisen <matthias at ccs.neu.edu>
wrote:

>
> and they may slow the program down, because they use to big-number
> multiplication immediately as opposed to small-number, built-in
> multiplication (and similar examples).
>

This can also be true for assignment-based programs which is
counter-intuitive to too many programmers. The idea is that you convert an
"inefficient" recursive program to a more "efficient" tail-recursive
program from which you can extract an even "more efficient" imperative
program. It turns out that the imperative program can actually be slower,
because of, as Matthias states, the operations used or simply because
imperative programs require more operations--extra operations not required
when you have referential transparency.

It's fascinating stuff to explore if you choose to continue this line of
thought.

Marco



>
>
>
>
>
>
>
>
>
>
>
> On Aug 8, 2014, at 12:00 PM, Jack Firth <jackhfirth at gmail.com> wrote:
>
> > As far as I understand it, the vast majority of the benefit of tail
> recursion is less the stack-frame business and more the ability to discard
> values you're not using anymore at each step by combining partial results.
> To clarify what I mean, for a function sum with a recursive and
> tail-recursive version:
> >
> > (define (sum xs)
> >   (if (empty? xs) 0 (+ (first xs) (sum (rest xs)))))
> >
> > (define (sum-tailrec xs)
> >   (let loop ([xs xs] [s 0])
> >     (if (empty? xs) s (loop (rest xs) (+ s (first xs))))))
> >
> > > (sum '(1 2 3))
> > => (+ 1 (sum '(2 3)))
> > => (+ 1 (+ 2 (sum '(3))))
> > => (+ 1 (+ 2 (+ 3  (sum '()))))
> > => (+ 1 (+ 2 (+ 3 0)))
> > => (+ 1 (+ 2 3))
> > => (+ 1 5)
> > 6
> >
> > > (sum-tailrec '(1 2 3))
> > => (loop '(1 2 3) 0)
> > => (loop '(2 3) 1)
> > => (loop '(3) 3)
> > => (loop '() 6)
> > 6
> >
> > The tail recursive version is much better because you can perform the
> calculation on parts of the list and then ditch those parts and accumulate
> your results as you go. But for functions which don't really have any means
> of accumulating their results, is there any advantage to tail recursion? If
> so, how much? For clarity, consider these two implementations of filter:
> >
> > (define (my-filter p xs)
> >   (cond
> >     [(empty? xs) xs]
> >     [(p (first xs)) (cons (first xs) (my-filter p (rest xs)))]
> >     [else (my-filter (rest xs))]))
> >
> > (define (my-filter-tail-rec p xs)
> >   (let loop ([xs xs] [filtered '()])
> >     (cond
> >       [(empty? xs) (reverse filtered)]
> >       [(p (first xs)) (loop (rest xs) (cons (first xs) filtered))]
> >       [else (loop (rest xs) filtered)])))
> >
> > > (my-filter even? '(1 2 3 4))
> > => (my-filter even? '(2 3 4))
> > => (cons 2 (my-filter even? '(3 4)))
> > => (cons 2 (my-filter even? '(4)))
> > => (cons 2 (cons 4 (my-filter even? '())))
> > => (cons 2 (cons 4 '()))
> > => (cons 2 '(4))
> > '(2 4)
> >
> > > (my-filter-tail-rec even? '(1 2 3))
> > => (loop '(1 2 3 4) '())
> > => (loop '(2 3 4) '())
> > => (loop '(3 4) '(2))
> > => (loop '(4) '(2))
> > => (loop '() '(4 2))
> > => (reverse '(4 2))
> > '(2 4)
> >
> > The tail recursion doesn't really help much in this problem, because the
> only real difference is that the tail recursive version holds the filtered
> values in a list instead of consing them on the stack. With the summing,
> you could take the values and combine them into something much more compact
> in terms of space by just summing them and passing the partial sum, but
> there is no logical "compacting" operation that can be done with filtering.
> So is there much of any performance or algorithmic difference between tail
> recursive and normal recursive functions when tail recursion is achieved
> simply by storing intermediate values in a list argument instead of consing
> them on the stack? And is that difference significant enough to justify the
> cost of reversing the list and the added complexity of writing the code in
> a tail recursive fashion?
> > ____________________
> >  Racket Users list:
> >  http://lists.racket-lang.org/users
>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>



-- 

Cheers,

Marco

Have a´¨)
¸.·´¸.·*´¨) ¸.·*¨)
(¸.·´ (¸.·´ * wonderful day! :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140808/5ef03c4c/attachment-0001.html>