CODEWITHSUNDEEP
recursionschemelisprackettail-recursion
Mateus Souza
Mateus Souza

Reputation: 11

Can this permutations-listing Racket function be made tail-recursive?

I wrote a function that receives a list and returns a list of all its permutations. It works like:

(define (remove-nth lst n) ; remove the nth element from a list lst
  (append (take lst n)
          (drop lst (+ 1 n))))

(define (perm lst) ; a list of all permutations of lst
  (if (null? (cdr lst))
      (list lst)
      (apply append (map (lambda (i)
                           (map (lambda (sublst) (cons (list-ref lst i)
                                                       sublst))
                                (perm (remove-nth lst i))))
                         (range (length lst))))))

Example:

> (perm '(1 2 3))
'((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Can it be made tail-recursive?

P.S. I know there is a permutations function in Racket. While it is tail-recursive, it uses a different algorithm. I'm curious if the one I wrote can also be made tail-recursive.

Upvotes: 1

Views: 169

Answers (1)

amalloy
amalloy

Reputation: 91907

Any recursive process can be made tail recursive, by explicitly moving to the heap any data that would otherwise be implicitly stored on the stack by recursive calls. Transformation to continuation-passing style is one common, mechanical way of doing this.

But it's not a particularly fruitful avenue to explore without a specific reason in mind. It allocates the same data, after all. And in the case of permutations, any algorithm that yields results as an ordinary list must take up a large amount of space, as there are a large number of results to produce. So, consider why you are asking this: what goal do you hope to achieve by making this tail recursive? With an answer to that, you can consider whether the goal is achievable.

Upvotes: 1

Related Questions