tail recursion in Scheme 
Author Message
 tail recursion in Scheme

>        (define (count n)
>            (cond
>                ((= n 0) nil)
>                (else

                    (cons n (count (- n 1))))))


>  If I understand things correctly, this is a tail-recursive
>  function.

No, this function is not tail-recursive.  For this, the recusive call (the second branch of "cond") would have to be the last function call within "count". Since the result of the recursive call is an argument to another function ("cons"), "count" is not tail-recursive it therefore needs stack-frames for its recursion.

A tail-recursive version of "count"

  (define (count' n)
     (count-aux n '())

  (define (count-aux n acc-lis)
     (if (= n 0)
         (count-aux (- n 1) (cons n acc-lis))))


Mon, 25 Jul 1994 22:16:25 GMT  
 tail recursion in Scheme


> A tail-recursive version of "count"
>   (define (count' n)
>      (count-aux n '())
>   (define (count-aux n acc-lis)
>      (if (= n 0)
>          acc-lis
>     (count-aux (- n 1) (cons n acc-lis))))

The main problem here is that this tail-recursive count function
doesn't do the same thing as the original -- its result is a list
of integers in ascending order and the original produced a list of
integers in descending order.
                                --Andrew Koenig

Tue, 26 Jul 1994 03:53:13 GMT  
 [ 2 post ] 

 Relevant Pages 

1. Tail-recursion in Scheme

2. tail recursion in Scheme

3. Tail recursion and complete recursion?

4. OO, lexical scope, closure, tail-recursion, continuation

5. Lisp type list, recursion and tail call optimisation

6. Tail recursion ???

7. Tail recursion

8. Thanks for the tail recursion

9. How is tail-recursion optimized in Smalltalk?

10. Any Smalltalk supporting tail recursion optimization ?

11. Tail-optimized recursion

12. tail recursion analysis


Powered by phpBB® Forum Software