Рекурсивное решение python для простой факторизации

Question

Я новичок в python и очень боюсь, пытаясь понять рекурсию. Я написал функцию, которая принимает одно целое число и возвращает список всех чисел в простой факторизации числа.

Я написал это итеративно:

def primeFac(n): 
    lst=[] 
    c=2 
    while c<=n: 
     if n%c==0: 
      n//=c 
      lst.append(c) 
     else: 
      c+=1 
    return lst 

который возвращает:

>>> primeFac(5) 
[5] 
>>> primeFac(72) 
[2, 2, 2, 3, 3] 

Как я могу сделать это рекурсивно? Это кажется ненужным, но мне нужно научиться делать это для моего окончательного экзамена.

Это то, что я написал до сих пор:

def primeFac(n): 
    lst = [] 
    c = 2 
    if n<=c: 
     lst.append(n) 
    else: 
     while n%c!=0: 
      c+=1 
     if n==c: 
      lst.append(n) 
     else: 
      lst.append(c) 
      lst.append(primeFac(n//c)) 
     return lst 

и я получаю:

>>> primeFac(5) 
[5] 
>>> primeFac(72) 
[2, [2, [2, [3, [3]]]]] 

Answer 1

код отлично подходит для этого, кроме:

lst.append(primeFac(n//c)) 
return lst 

вы добавите возврат , и верните список, поэтому вы добавите список в свой список, на «обычную» итерацию, которую вы использовали:

lst.append(c) 

так что вы добавляли только значение.

вы можете сделать так, чтобы сцепить списки:

lst = lst + primeFac(n//c))