def merge(L1, L2):
    if not L1:      # se L1 è vuota torno L2
        
        return L2
    if not L2:
        return L1   # se L2 è vuota torno L1
    primo1 = L1[0]
    resto1 = L1[1:]
    primo2 = L2[0]
    resto2 = L2[1:]
    if primo1 < primo2:
        return [primo1] + merge(resto1, L2)
    else:
        return [primo2] + merge(L1, resto2)


def merge2(L1, L2, livello=0):
    print('  '*livello, 'entering', L1, L2)
    if not L1:      # se L1 è vuota torno L2
        ris = L2
    elif not L2:
        ris = L1   # se L2 è vuota torno L1
    else:
        primo1 = L1[0]
        resto1 = L1[1:]
        primo2 = L2[0]
        resto2 = L2[1:]
        if primo1 < primo2:
            ris = [primo1] + merge2(resto1, L2, livello+1)
        else:
            ris = [primo2] + merge2(L1, resto2, livello+1)
    print('  '*livello, 'exiting', ris)
    return ris

def MergeSort(L):
    if len(L) < 2:
        return L
    mezzo = len(L) // 2         # indice centrale
    prima = L[:mezzo]           # prima metà di L
    seconda = L[mezzo:]         # seconda metà di L
    prima_ordinata = MergeSort(prima)
    seconda_ordinata = MergeSort(seconda)
    return merge(prima_ordinata, seconda_ordinata)

def MergeSort2(L, livello=0):
    print('  '*livello, 'entering', L)
    if len(L) < 2:
        ris = L
    else:
        mezzo = len(L) // 2         # indice centrale
        prima = L[:mezzo]           # prima metà di L
        seconda = L[mezzo:]         # seconda metà di L
        prima_ordinata = MergeSort2(prima, livello+1)
        seconda_ordinata = MergeSort2(seconda, livello+1)
        ris = merge(prima_ordinata, seconda_ordinata)
    print('  '*livello, 'exiting', ris)
    return ris



def MCD(x, y):
    if x == y:
        return x
    if x < y:
        return MCD( x, y-x)
    else:
        return MCD( y, x-y)

    
def MCD2(x, y, livello=0):
    print('  '*livello, 'entering', x, y)
    if x == 0:
        ris = y
    elif y == 0:
        ris = x
    elif x < y:
        ris = MCD2( x, y%x, livello+1)
    else:
        ris = MCD2( y, x%y, livello+1)
    print('  '*livello, 'exiting', ris)
    return ris

def stampa_a_rovescio(L):
    if not L:
        return
    else:
        print(L.pop())
        stampa_a_rovescio(L)


def stampa_a_rovescio2(L, livello=0):
    print('  '*livello, 'entering', L)    
    if not L:
        return
    else:
        print(L.pop())
        stampa_a_rovescio2(L, livello+1)
    print('  '*livello, 'exiting')

def stampa_a_rovescio4(L, livello=0):
    print('  '*livello, 'entering', L)    
    if not L:
        return
    stampa_a_rovescio4(L[1:], livello+1)
    print(L[0])
    print('  '*livello, 'exiting')


import random

if __name__ == '__main__':
    stampa_a_rovescio4([1, 2, 3, 4, 5])