How to deal with this exercise using recursion in Python?

def exercise(a, polish=sorted):
  if not isinstance(a, list):
    return 1, a, {a}
  a.reverse()
  amount, sum, numbers = 0, 0, set()
  for b in a:
    a, s, n = exercise(b, set)
    amount += a
    sum += s
    numbers |= n
  return amount, sum, polish(numbers)

Or with a little helper doing the reversals and collecting the numbers:

def exercise(a):
  def go(a):
    if isinstance(a, list):
      a.reverse()
      for b in a:
        go(b)
    else:
      numbers.append(a)
  numbers = []
  go(a)
  return len(numbers), sum(numbers), sorted(set(numbers))

Demo:

lista = [3, 3, 5, [[1, 8, [9, 3]], 3, [2, [9, [5, 6],[9]] ] ]]

>>> exercise(lista)
(13, 66, [1, 2, 3, 5, 6, 8, 9])

>>> lista
[[[[[9], [6, 5], 9], 2], 3, [[3, 9], 8, 1]], 5, 3, 3]

You are using recursion just fine in the reverse function, just use recursion in you exercise function:

def exercise(lista): 
    lista_ordinata = []
    count = 0
    somma = 0
    # reverse_list(lista)
    
    for x in lista:
        if isinstance(x, list):
            recursion = exercise(x) # call recursion until you have a list with only integers
            # and add the result to your running totals
            count += recursion[0]
            somma += recursion[1]
            lista_ordinata.extend(recursion[2])
        else:
            count += 1
            somma += x
            lista_ordinata.append(x)
    
    lista_ordinata = sorted(list(set(lista_ordinata)))
    
    return count, somma, lista_ordinata

print(exercise(lista))

(13, 66, [1, 2, 3, 5, 6, 8, 9])

Here's a way without any loops at all.

First of all, we can have a definition for a partial insertion sort, which inserts any value to its correct position in an existing sorted array.

def partialInsertionSort(val, idx, sortarr):
    if idx == len(sortarr):
        sortarr.append(val)
    elif val < sortarr[idx]:
        sortarr.insert(idx, val)
    elif val > sortarr[idx]:
        sortarr = partialInsertionSort(val, idx+1, sortarr)

    return sortarr

As you travel through any list a, unless you've reached the end of a, there are two possibilities:

• The current item is another list -> Recurse through the sublist!
• The current item is a digit -> Increment total and count. If this digit is a previously unseen digit, 'insert' it to your list of sorted digits.

Done with the above two possible options, you have thus processed the current element, and can move to the next element by incrementing the index i.

def reverse_and_sort(a, i, out, sortarr, total, count):
    if i==len(a): 
        return out, sortarr, total, count

    if isinstance(a[i], list):
        a[i], sortarr, total, count = reverse_and_sort(a[i], 0, [], sortarr, total, count)
    else:
        total += a[i]
        count += 1
        if a[i] not in sortarr:
            sortarr = partialInsertionSort(a[i], 0, sortarr)

    out.insert(0, a[i])
    return reverse_and_sort(a, i+1, out, sortarr, total, count)

Test:

rev, srt, total, count = reverse_and_sort(lista, 0, [], [], 0, 0)
print(rev)    #[[[[[9], [6, 5], 9], 2], 3, [[3, 9], 8, 1]], 5, 3, 3]
print(srt)    #[1, 2, 3, 5, 6, 8, 9]
print(total)  #66
print(count)  #13

A relatively short version, which uses the add operator is given by that:

from operator import add

def sorter(l):
    if isinstance(l, list):
        temp = [0, 0, []]
        for e in map(sorter, l):
            temp = list(map(add, e, temp))
        return temp[0], temp[1], sorted(set(temp[2]))
    return 1, l, [l]

It should give the correct result:

test_list = [[[[[9], [6, 5], 9], 2], 3, [[3, 9], 8, 1]], 5, 3, 3]
sorter(test_list)

>>> (13, 66, [1, 2, 3, 5, 6, 8, 9])

Two liner approach!

Here is a simple solution to the problem, using indirect recursion. Indirect recursion is where a function f(x) calls a function g(x) which in turn calls f(x).

If your problem was just the first part, the solution is just a simple 2 liner -

f = lambda x: [g(i) for i in reversed(x)]
g = lambda x: f(x) if type(x)==list else x

f(lista)

[[[[[9], [6, 5], 9], 2], 3, [[3, 9], 8, 1]], 5, 3, 3]

Beautiful right?

The main idea here is that at an element level you just need to check if the element is an integer and return it, else you need to use another function that lets you iterate over the list. You can have counters at the level of the second function which lets you track the sum and the count and return it with the final function call.

Since you also have the 2nd part to the solution which is using a few counters, you can modify the above code for g(x) to incorporate that as below -

cnt = []
sm = []

#function to iterate over a reversed list
f = lambda x: [g(i) for i in reversed(x)]

#function to call f if list else updated counters and return element
def g(x):
    if type(x)==list:
        return f(x)
    else: 
        cnt.append(1)  #ONLY MODIFICATION
        sm.append(x)   #ONLY MODIFICATION    
        return x
    
#call f and return sum of counters
def rec(l):
    o = f(l)
    return o, (sum(cnt), sum(sm), sorted(sm))


out, tup = rec(lista)

print(out)
print(tup)

[[[[[9], [6, 5], 9], 2], 3, [[3, 9], 8, 1]], 5, 3, 3]

(13, 66, [1, 2, 3, 3, 3, 3, 5, 5, 6, 8, 9, 9, 9])

def exercise(lista, total = 0, count = 0, all_int = []):
  for item in lista:
    if isinstance(item, list):
      count, total, all_int = exercise(item, total, count, all_int)
    elif isinstance(item, int):
      total += item
      count += 1
      if item not in all_int:
        all_int.append(item)
        all_int.sort()
  lista.reverse()
  return count, total, all_int

Maybe this would help :)

def exercise (lista):
    reverse_list(lista)
    r = count_numbers(lista), sum_numbers(lista), sorted(pull_out(lista))
    return r



def is_list (lista):
    return isinstance(lista,list)

def reverse_list(lista):
    lista_nuova = []
    for e in lista[::-1]:
        if is_list(e):
            lista_nuova.append(reverse_list(e))
        else:
            lista_nuova.append(e)
    return lista_nuova


def count_numbers(lista):
    c = 0
    for e in lista:
        if is_list(e):
            c += count_numbers(e)
        else:
            c+=1
    return c

def sum_numbers(lista):
    s = 0
    for e in lista:
        if is_list(e):
            s += sum_numbers(e)
        else:
            s+=e
    return s

def pull_out(lista):
    b_lista = []
    for e in lista:
        if is_list(e):
            b_lista.extend(pull_out(e))
        else:
            b_lista.append(e)
    return b_lista


lista = [3, 3, 5, [[1, 8, [9, 3]], 3, [2, [9, [5, 6],[9]] ] ]]
r = exercise(lista)
print(r)
# (13, 66, [1, 2, 3, 3, 3, 3, 5, 5, 6, 8, 9, 9, 9])

I did it with separate functions for clarity.