Making recursive function more elegant

Question

I've been working to hone my understanding of recursion [and become a better programmer in general]. Today a wrote some code to flatten a tuple of tuples. The code is as follows:

def recursive_tuple_flatten(tuple_list):
    if type(tuple_list) is tuple:
        if type(tuple_list[0]) is tuple:
            list_of_lists = [list(tuple_list[0]), tuple_list[1:]]
            return recursive_tuple_flatten([i for j in list_of_lists for i in j])
        else:
            return recursive_tuple_flatten(list(tuple_list))
    else:
        if type(tuple_list[-1]) is tuple:
            list_of_lists = [tuple_list[:-1], list(tuple_list[-1])]
            return recursive_tuple_flatten([i for j in list_of_lists for i in j])
        else:
            return tuple_list

k = ((1,(2)),(3,(4,5)))
recursive_tuple_flatten(k)

The code works, but I'd really appreciate any advise and coaching to help me improve this code and make it more elegant. Have a great day!

This probably belongs on https://codereview.stackexchange.com. _I've been working to hone my understanding of recursion_ You should consider using a different language, recursion in Python is far from standard. — AMC, Jun 03 '20 at 01:19
Also, `(2)` isn't a tuple, did you mean `(2,)` ? When that is fixed, the output of the function becomes `[1, (2,), 3, 4, 5]`, which is incorrect. — AMC, Jun 03 '20 at 01:27
I didn't think of checking this earlier, it appears this question might essentially be a duplicate of https://stackoverflow.com/questions/2158395/flatten-an-irregular-list-of-lists (and a few more). — AMC, Jun 03 '20 at 01:42
You're right. In this case my function doesn't work at all. Shoot. Thanks for pointing this out. — C L, Jun 03 '20 at 01:45
Yes, this answers it. Apologies for my ignorance. This is my first post. How do I close out the question? — C L, Jun 03 '20 at 01:48

Derek 朕會功夫 · Answer 1 · 2020-06-03T01:24:27.750

Divide and conquer is a common technique when coming up with a recursive algorithm. In your example prompt, the function should just iterate over all the values in a list and call itself with an array size that is slight smaller. Eventually it will reach a size of 0 (a single value) and you're done.

I haven't written Python code in a long time. Assuming this is a general question on recursive algorithms, this would be how it looks in JavaScript (should be self-explanatory - think of it as pseudocode):

function flatten(arr) {
  if (!Array.isArray(arr)) return [arr];
  return arr.reduce((acc, cur) => [...acc, ...flatten(cur)], []);
}

const input = [[1,[2]],[3,[4,5]]];
const output = flatten([[1,[2]],[3,[4,5]]]);

console.log(output);

Let me know if you need a solid example in Python.

These steps might help you in coming up with a elegant recursive solution to a problem:

Find a way to reduce the input size n. By induction you can assume your function is already implemented for n - 1
Figure out how to combine the results of smaller input sizes together. This is the "divide and conquer" part.
Determine the base case. Your recursive function needs to stop at some point.

score 1 · Accepted Answer · answered Jun 03 '20 at 01:30

1

While this probably belongs on Code Review, here is what I came up with, for the sake of it:

def recursive_tuple_flatten(tuples):
    res = []
    for elem in tuples:
        if isinstance(elem, tuple):
            res.extend(recursive_tuple_flatten(elem))
        else:
            res.append(elem)
    return res

answered Jun 03 '20 at 01:30

AMC

2,642
7
13
35

Thanks AMC this is great! And also thank you for the heads up regarding posting to Code Review. This was my first post and I will make sure I post to right forum next time. – C L Jun 03 '20 at 01:38

Making recursive function more elegant

2 Answers2