[Python] flatten 구현 - non-iterative, recursive function

import time

def flatten(lst):
    ret = []
    i = 0
    while i < len(lst):
        if isinstance(lst[i], list):
            ret.extend(flatten(lst[i]))
        else:
            ret.append(lst[i])
        i += 1
    
    return ret

if __name__ == "__main__":
    start = time.time()
    data = [1,[-2,[[4]], [0,5], [],3],[4],2,7] * 1000000
    sum = 0
    result = flatten(data)
    i = 0
    while True:
        e = result[i]
        print(e, end=' ')
        sum += e
        if sum > 10:
            break
        i += 1
        
    print('\nResult :', sum)
    print(f'time : {(time.time()-start) * 1000}')
#경과 시간 : 5500ms(data를 1,000,000배하여 진행)

 

주어진 리스트를 while을 통해 반복하면서 원소의 타입이 리스트라면 그 리스트를 recursion하여 그 리스트를 flatten합니다.

 

원소의 타입이 리스트가 아니라면 ret 리스트에 그 값을 추가시킵니다.

 

while이 끝났다면 이를 통해 얻어지는 ret 리스트를 반환하여 flattened 리스트를 가져옵니다.