1

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

  • The permutations of a one-element list is a list of itself.
  • The permutations of an n-element list are each element followed by the permutations of the list with the element removed.
(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.

Mateus Souza
  • 11
  • 1
  • 1
    related: https://stackoverflow.com/a/49907365/849891. – Will Ness Aug 18 '21 at 21:35
  • Yes, every program can be written as iterative process, either by writing it directly, or by using automatic conversion. See for example CPS rewriting. The current continuation being explicit, you can choose directy what to be computed next, and you can choose such that to make it tail-recursive. – alinsoar Aug 20 '21 at 11:01

1 Answers1

1

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.

amalloy
  • 89,153
  • 8
  • 140
  • 205