Konstigt namn eftersom det inte har med primtal att göra. Jag kallar den factors(n,f) i stället.
Rekursiv betyder att den ska anropa sej själv, alltså vara av typen
def factors(n,f):
    - - -
    b=factors(..,..)
    - - -
    return factorlist

Det rekursiva anropet ska vara ett enklare problem, till exempel factors(n-1,f) eller factors(n,f+1).
I det här fallet är den senare lämplig. En rekursiv tanke är så här:
"Faktorlistan (n,f) är oftast samma som faktorlistan (n,f+1), men om f är en faktor i n ska man lägga till f först i listan."
Och så måste man ha ett basfall och det är när f>n, för då blir listan tom.
def factors(n,f):
    if f>n: return []
    b=factors(n,f+1)
    if .... : b=[f]+b     # om f delar n
    return b

Pistolero skrev:

wow_08 skrev:

Hej!

Skulle någon kunna hjälpa mig med följande uppgift? Jag vet inte hur jag ska tänka här

Skriv en rekursiv funktion, almostPrime(i, f) som returnerar en lista med tal som talet i är jämt delbara med. Listan ska innehålla alla tal från och med f till och i, som i är jämt delbara med. Exempel:
   >>> almostPrimeFact(111,2)
   [3, 37, 111]
   >>> almostPrimeFact(38,2)
   [2, 19, 38]
   >>> almostPrimeFact(38,3)
   [19, 38]
   >>>

När du ska göra en rekursiv funktion så återanvänder du samma funktion. Funktionen anropar alltså sig själv och på så viss kan ett stort problem göras till ett litet.

Om vi kollar på en icke-rekursiv funktion, så får vi följande:

Kod:

def almostPrimeFact(i, f):
    arr = []
    for x in range(f, i+1):
        if i%x == 0:
            arr.append(x)
    return arr

print( almostPrimeFact(111, 2) )
print( almostPrimeFact(38, 2) )
print( almostPrimeFact(38, 3) )

För att göra det rekusivt måste funktionen anropa sig själv. Det innebär att man måste ha ett basfall 0! och resterande körs rekusivt n!.

Vi kan ha basfallet att i%f == 0, vilket innebär att i/f ger ett heltal när i%f == 0. Om fallet inte är den, då kan vi återanropa funktionen och testa på nytt genom att höja upp i ett steg. För att det inte ska vara oändligt (för det måste stanna nån gång), så kan man lägga in en if-sats att i > f.

Vi får då en rekusiv funktion:

Kod:

def almostPrimeFact(i, f):
    arr = []
    if i%f == 0:
        arr.append(f)
    if i > f:
        arr.extend(almostPrimeFact(i, f+1))
    return arr

print( almostPrimeFact(111, 2) )
print( almostPrimeFact(38, 2) )
print( almostPrimeFact(38, 3) )

Det som händer är följande:
Steg 1: almostPrimeFact(111, 2) => i%f == 0 är falst, i > f är sant, vilket gör att almostPrimeFact(i, f+1) körs.
Steg 2: almostPrimeFact(111, 3) => i%f == 0 är sant och vi lägger in f i listan, i > f är också sant, vilket gör att vi kör almostPrimeFact(i, f+1).
Steg 3: almostPrimeFact(111, 4) => i%f == 0 är falskt, i > f är sant så vi kör almostPrimeFact(i, f+1).
Steg 4: almostPrimeFact(111, 5) => i%f == 0 är falskt, i > f är sant.
Steg 5: almostPrimeFact(111, 6) => i%f == 0 är falskt, i > f är sant.
o.s.v.
Steg 36: almostPrimeFact(111, 37) => i%f == 0 är sant, så vi sparar 37 i listan, i > f är sant.
Steg 37: almostPrimeFact(111, 38) => i%f == 0 är falskt, i > f är sant.
Steg 38: almostPrimeFact(111, 39) => i%f == 0 är falskt, i > f är sant.
o.s.v.
Steg 110: almostPrimeFact(111, 111) => i%f == 0 är sant, så vi sparar det i listan, i > f är falskt, så vi kör inte if-satsen, och därför avslutas funktionen och vi erhåller listan [3, 37, 111]

Både den icke-rekusiva och den rekusiva funktionen utför precis samma sak. Vilket man föredrar att använda är en smaksak. Dock kan rekusiv funktion vara mer lämplig vid lite mer svårare uppgifter, t.ex. om man vill göra ett program som löser sudoku. Då räcker det med några rader kod med binära sökträd, istället för att kämpa sig igenom med icke-rekusiva funktioner i form av massor av for-loopar, där man snabbt tappar bort sig i röran.

Bara fliker in lite allmänt:

Ditt tänk är i princip iterativt. Rekursion är en helt annan problemlösningsstrategi och man bör inte öht blanda in eller jämföra med iterativ kod. Med detta tänk löser man knappast bland de enklare rekursiva problem.

Jag tycker Henriks inlägg efterliknar det rekursiva tänket mycket mer.

När vi designar rekursiva algoritmer är basfallen de fall Där vi direkt kan svara på frågan / lösa problemen. Kan vi inte det, vill vi bryta ned vårt problem till en mindre instans I SAMMA FORM. Det mindre problemet löser vi genom att anropa rekursivt. Det slutgiltliga steget blir att skapa en lösning på originala problemet mha sina delllösningar.