# works from last element to first
def partition1(li, f):
    if len(li) == 0:
        return [], []
    x, *xs = li
    ys, zs = partition1(xs, f)
    print(ys, zs)
    if f(x):
        return [x, *ys], zs
    return ys, [x, *zs]
    
# works from first element to last    
def partition2(li, f, ys=[], zs=[]):
    if len(li) == 0:
        return ys, zs
    x, *xs = li
    print(ys, zs)
    if f(x):
        return partition2(xs, f, [*ys, x], zs)
    return partition2(xs, f, ys, [*zs, x])
    
li = [1,2,3,4,5,6,7]
print(partition1(li, lambda x: x % 2))
print(partition2(li, lambda x: x % 2))