Nyckelord: funktioner
Även 0! är definierat och är lika med 1. Låt därför basfallen vara n = 0 och n = 1. Den rekursiva lösningen passar små tal; stora tal kan överskrida Pythons rekursionsgräns.
Räkna ut fakultet med rekursiva funktioner
I denna uppgift ska vi skapa en funktion som räknar ut fakulteten av ett tal. Vi ska göra detta genom att skapa ett program som anropar en funktion rekursivt.
Fakultet är en funktion inom matematiken. För ett heltal större än noll är fakulteten lika med produkten av alla heltal från 1 upp till och med talet självt.
-Wikipedia
Fakultet definieras enligt:
n! = 1 * 2 * 3 * ... * (n - 1) * n
Exempelvis:
4! = 1 * 2 * 3 * 4 = 24
För att skapa en metod som anropar sig själv rekursivt behöver vi tänka på:
- Hur hanterar vi basfallen n = 0 och n = 1?
- Hur löser vi alla andra fall än basfallet?
Använd en variabel n av datatypen int som input till funktionen. Testa sedan olika värden på n för att se om metoden fungerar som den ska.
Ledtråd
Basfallet, då n = 1, ska vi returnera 1. I alla övriga fall kan vi skriva om definitionen för fakultet enligt:
Svar
def factorial(n):
if type(n) is not int or n < 0:
raise ValueError("n måste vara ett icke-negativt heltal")
if n <= 1:
return 1
return n * factorial(n - 1)
if __name__ == "__main__":
n = 5
print(f"Fakulteten av {n} är: {factorial(n)}")Förklaring:
Basfallen är 0! = 1 och 1! = 1. Vi returnerar därför 1 om n är 0 eller 1.
Fakultet kan beskrivas med uttrycket
Vi kan alltså i alla andra fall än basfallet anropa fakultet-metoden igen med inputen (n-1).
Programmet körs alltså enligt:
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
return 1
return 2*1 = 2
return 3*2 = 6
return 4*6 = 24
return 5*24 = 120Och så vidare beroende på vad du tilldelar för värde på n.