Rekursiva funktioner

Håll i dig, för nu kommer en liten delikatess, som kanske får hjärnan att överhettas och kommer det att pumpa ut rök ur dina öron. Funktioner kan anropa sig själva.

 >>> def fakultet(n):
 ... if n == 0:
 ...     return 1
 ... else:
 ...     return n * fakultet(n - 1)
 ...

Anropa funktionen:

>>> fakultet(3)
6
>>> fakultet(5)
120
>>> fakultet(10)
3628800
>>>

Vill du kontrollräkna på räknedosan så står det nog x! eller n! på knappen för fakultet.

dsc_6298.nef_9QH0UW

Hur funkar det? Vi beräknar fakultet(3): n är skilt från 0, så då är det samma sak som 3 * fakultet(2), och då får vi räkna ut det… 2 är också skilt från noll, så då är
svaret 2 * fakultet(1). fakultet(1) är 1 * fakultet(0) och fakultet(0) är ju ett, så svaret blir då 1. Nu poppar svaret fram fakultet(3) = 3 * 2 * 1 * 1.

Nu hade just det här problemet antagligen lösts snyggare och effektivare med en loop eller genom att i förväg lagra in svaren i en lista. Ändå är rekursioner en metod som man då och då kan vilja ta till för att skapa en kompakt och elegant lösning på olika typer av problem. Tycker du att det här var kul, så är du att gratulera. Tycker du att det bara var obegripligt så kan jag trösta dig med att man kan göra väldigt mycket i programmmeringsväg utan rekursioner också.

Du kommer å andra sidan snart att upptäcka att också andra problem än matematiska dito gärna löses med en rekursion.

Övning:

  • Testa funktionen ovan med olika värden på n. Hur stora n kan du beräkna fakulteten för?
  • Skriv om funktionen ovan utan att använda rekursion.
  • Skriv en annan rekursiv funktion leta gärna i någon mattebok efter ett lämpligt ”offer”