<div dir="ltr">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:<br>
<br>(define (sum xs)<br>  (if (empty? xs) 0 (+ (first xs) (sum (rest xs)))))<br><br>(define (sum-tailrec xs)<br>  (let loop ([xs xs] [s 0])<br>    (if (empty? xs) s (loop (rest xs) (+ s (first xs))))))<div><br></div><div>
> (sum '(1 2 3))<br>=> (+ 1 (sum '(2 3)))<br>=> (+ 1 (+ 2 (sum '(3))))<br>=> (+ 1 (+ 2 (+ 3  (sum '()))))<br>=> (+ 1 (+ 2 (+ 3 0)))<br>=> (+ 1 (+ 2 3))<br>=> (+ 1 5)<br>6</div><div><br>
</div><div>> (sum-tailrec '(1 2 3))<br>=> (loop '(1 2 3) 0)<br>=> (loop '(2 3) 1)<br>=> (loop '(3) 3)<br>=> (loop '() 6)<br>6</div><div><br></div><div>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:<br>
<br>(define (my-filter p xs)<br>  (cond<br>    [(empty? xs) xs]</div><div>    [(p (first xs)) (cons (first xs) (my-filter p (rest xs)))]</div><div>    [else (my-filter (rest xs))]))<br><br>(define (my-filter-tail-rec p xs)<br>
  (let loop ([xs xs] [filtered '()])<br>    (cond<br></div><div>      [(empty? xs) (reverse filtered)]<br>      [(p (first xs)) (loop (rest xs) (cons (first xs) filtered))]</div><div>      [else (loop (rest xs) filtered)])))</div>
<div><br></div><div>> (my-filter even? '(1 2 3 4))<br>=> (my-filter even? '(2 3 4))<br>=> (cons 2 (my-filter even? '(3 4)))<br>=> (cons 2 (my-filter even? '(4)))</div><div>=> (cons 2 (cons 4 (my-filter even? '())))</div>
<div>=> (cons 2 (cons 4 '()))</div><div>=> (cons 2 '(4))</div><div>'(2 4)<br><br>> (my-filter-tail-rec even? '(1 2 3))<br>=> (loop '(1 2 3 4) '())<br>=> (loop '(2 3 4) '())</div>
<div>=> (loop '(3 4) '(2))</div><div>=> (loop '(4) '(2))</div><div>=> (loop '() '(4 2))</div><div>=> (reverse '(4 2))</div><div>'(2 4)</div><div><br></div><div>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?</div>
</div>