Replacing a for loop with tail recursion in a recursive function

Question

I'm trying to make the following function completely tail recursive, e.g. get that pesky for loop out of there. Reason being is that I'm trying to easily convert the solution to an iterative one involving the use of an explicit stack. Please advise.

def permutations(A):
    P = []
    P2 = []
    permutations_recursive(A, [], P)
    permutations_tail_recursive(A, [], P2, 0)
    print(P2)
    return P

def permutations_recursive(first, last, perms):
    if len(first) == 0:
        perms.append(last)
    else:
        for i in range(len(first)):
            permutations_recursive(
                first[:i] + first[i+1:],
                last + [first[i]],
                perms)

With list-comprehension you can get rid of most simple for and while loops and such. but in fact its still a loop. Anyways dig into list-comp and u will understand ;) — The Fool, Sep 12 '18 at 18:16

score 0 · Accepted Answer · answered Sep 12 '18 at 18:44

0

Close iterative analog:

def permutations(A):
    P = []
    permutationsI(A, P)
    print(P)

def permutationsI(A, perms):
   stack = [(A, [])]
    while len(stack):
        first, last = stack.pop()
        if len(first):
            for i in range(len(first)):
                stack.append((first[:i] + first[i+1:],last + [first[i]]))
        else:
            perms.append(last)

permutations([1,2,3])
>>[[3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]

answered Sep 12 '18 at 18:44

MBo

77,366
5
53
86

This may be the iterative process the asker ultimately aims to reach, but it does not provide a tail-recursive function that the question asks for. – Mulan Sep 12 '18 at 23:30

bugMiner · Answer 2 · 2018-09-16T13:29:57.343

A fully recursive function should be:

def permutations_comp_recursive(first, last, perms, i):
    if len(first) == 0:
        perms.append(last)
    elif i == len(first):
        pass
    else:
        permutations_comp_recursive(first, last, perms, i+1)
        if first:
                permutations_comp_recursive(
                first[:i]+first[i+1:],
                last + [first[i]],
                perms, 0)

For good performance i recommand numpy solutions.

Edit 1: Now the following should be tail-recursive, with the use of list comprehensions. This uses a workarount for tail-recursion in python (and the last 2 arguments were omitted - the result is passed as return value):

import itertools as it
class Recurse(Exception):
    def __init__(self, *args, **kwargs):
        self.args = args
        self.kwargs = kwargs

def recurse(*args, **kwargs):
    raise Recurse(*args, **kwargs)

def tail_recursive(f):
    def decorated(*args, **kwargs):
        while True:
            try:
                return f(*args, **kwargs)
            except Recurse as r:
                args = r.args
                kwargs = r.kwargs
                continue
    return decorated

@tail_recursive
def permutations_tail_recursive(first, last, direct=False):
    if len(first) == 0 or not all(first):
        return last
    else:
        l = len(first[0]) if direct else len(first)
        if last:
            return recurse([fi[:i]+fi[i+1:] for fi, i in it.product(first, range(l))],
                [last[j] + first[j][i] for j, i in it.product(range(len(last)), range(l))], True)
        else:
            return recurse([first[:i]+first[i+1:] for i in range(l)],
                [first[i] for i in range(l)], True)

This is not optimised and uses loops. Im not sure if this and the code without loop above can be combined - might look into it again. itertools.permutations can be used for this application.

What does *"fully recursive"* mean? The definition in this answer does not use tail recursion. — Mulan, Sep 12 '18 at 23:28
Hi, am i ment "completly recursive" without loops. So well the secound if statement is the problem right? And it should use a return chain instead of the perms list. I will try to fix this when i have time. — bugMiner, Sep 13 '18 at 23:46

Replacing a for loop with tail recursion in a recursive function

2 Answers2