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
– The Fool, Commented Sep 12, 2018 at 18:16

MBo · Accepted Answer · 2018-09-12 18:44:36Z

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, 2018 at 18:44

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mulan Over a year ago

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.

bugMiner · Accepted Answer · 2018-09-16 13:29:57Z

0

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.

edited Sep 16, 2018 at 13:29

answered Sep 12, 2018 at 20:49

bugMiner

213 bronze badges

2 Comments

Mulan Over a year ago

What does "fully recursive" mean? The definition in this answer does not use tail recursion.

bugMiner Over a year ago

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.

Collectives™ on Stack Overflow

Replacing a for loop with tail recursion in a recursive function

2 Answers 2

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related