Cartesian product of two tuples - python I'm solving exercise 4 from Discussion 3 of Berkley's CS 61A (2012) (see page 4):

Fill in the definition of cartesian_product. cartesian_product takes in two tuples and returns a tuple that is the Cartesian product of those tuples. To find the Cartesian product of tuple X and tuple Y, you take the first element in X and pair it up with all the elements in Y. Then, you take the second element in X and pair it up with all the elements in Y, and so on.
def cartesian_product(tup_1, tup_2):
    &quot;&quot;&quot;Returns a tuple that is the cartesian product of tup_1 and tup_2.
    &gt;&gt;&gt; X = (1, 2)
    &gt;&gt;&gt; Y = (4, 5)
    &gt;&gt;&gt; cartesian_product(X, Y)
    ((1, 4), (4, 1) (1, 5), (5, 1), (2, 4), (4, 2) (2, 5), (5, 2))
    &quot;&quot;&quot;


My solution:
def cartesian_product_recursive(tup_1, tup_2):
    &quot;&quot;&quot;Returns a tuple that is the cartesian product of tup_1 and tup_2
    
    &gt;&gt;&gt; X = (1, 2)
    &gt;&gt;&gt; Y = (4, 5)
    &gt;&gt;&gt; cartesian_product(X, Y)
    ((1, 4), (4, 1), (1, 5), (5, 1), (2, 4), (4, 2), (2, 5), (5, 2))
    &quot;&quot;&quot;
    length1 = len(tup_1)
    length2 = len(tup_2)
    def product(tup_1, tup_2, index1, index2):
        if index1 == length1:
            return ()
        elif index2 == length2:
            return product(tup_1, tup_2, index1 + 1, 0)
        else:
            return ((tup_1[index1], tup_2[index2]),) + ((tup_2[index2], tup_1[index1]), ) + product(tup_1, tup_2, index1, index2 + 1)
    return product(tup_1, tup_2, 0, 0)

I know that Python has a built-in function itertools.product, but at this point in the course, the only operations on tuples that we have studied are indexing [1] [-1], slicing [1:], and concatenation +, so my solution needs to restrict itself accordingly.
Can this solution be improved?
If you can use the built-in itertools module, then itertools.product is probably the easiest, but it probably not allowed.  itertools.product creates an iterable of the cartesion product of two sequences.  Since you want it with both the tup1 element first and the tup2 element first, you need to do it twice:

def cartesian_product_itertools(tup1, tup2):
    return tuple(product(tup1, tup2))+tuple(product(tup2, tup1))


The second approach would be to roll your own generator-based solution, using the yield statement.  This can then be converted to a tuple in the same way.  You need an inner function to handle the generator, and an outer function to convert it to a tuple:

def cartesian_product_iter(tup1, tup2):
    def cartesian_product_iter_inner(tup1, tup2):
        for t1 in tup1:
            for t2 in tup2:
                yield t1, t2
                yield t2, t1
    return tuple(cartesian_product_iter(tup1, tup2))


You can also do a similar looping version:

def cartesian_product_loop(tup1, tup2):
    res = ()
    for t1 in tup1:
        for t2 in tup2:
            res += ((t1, t2), (t2, t1))
    return res


For a recursive version, you can greatly simplify by using slices instead of indexes:

def cartesian_product_recursive(tup_1, tup_2):
    res = ((tup_1[0], tup_2[0]), (tup_2[0], tup_1[0]))
    if len(tup_2) == 1:
        return res
    res += cartesian_product_recursive(tup_1[:1], tup_2[1:])
    if len(tup_1) == 1:
        return res
    res += cartesian_product_recursive(tup_1[1:], tup_2)
    return res


I prefer short-circuiting, hence the returns.  If you prefer if...else, here is an equivalent implementation:

def cartesian_product_recursive_2(tup_1, tup_2):
    res = ((tup_1[0], tup_2[0]), (tup_2[0], tup_1[0]))
    if len(tup_2) &gt; 1:
        res += cartesian_product_recursive_2(tup_1[:1], tup_2[1:])
    if len(tup_1) &gt; 1:
        res += cartesian_product_recursive_2(tup_1[1:], tup_2)
    return res