sslug-teknik team mailing list archive

[Henning Niss <hniss@xxxxxxx>]

"Keld Laursen" <kl@xxxxxxxxxx> writes:

> > ``kernesprog'' (the Bare language); de foreskriver faktisk den
> > halerekursive version.
> 
> Og hvad er så en halerekursiv funktion?

Det er faktisk et rigtigt godt spørgsmål (i.e., det er svært at
definere helt præcist). Intutitivt er det dog ikke så svært (synes jeg
:-)). 

Husk på at i SML (og andre funktionsprogrammeringssprog) udtrykker men
(næsten) alle løkke-kontrolstrukturer som funktioner der kalder
hinanden eller sig selv. F.eks. som Mads' oprindelige fak funktion der
så cirka sådan her ud

  fun fak n = if n = 0 then 1 else n * fak(n-1)

Her kalder fak sig selv rekursivt (med fak(n-1)). Dette rekursive kald
forekommer i en kontekst hvor returværdien deltager i en ny operation
(gang med n). Med andre ord, hver rekursiv instans kalder sig selv for
at gøre noget og slutter af med at gange med n. Dette er *ikke* en
halerekursiv funktion.

En halerekursiv funktion er sådan en fyr der blot returnerer lige
efter det rekursive kald. Altså, hvis man er ved at definere
funktionen f, må man ikke have kald af formen ... f x ... hvor
prikkerne bruger returværdien. Vi kan omskrive fak til at bruge en
``akkumulator''

  fun accfak (n, acc) = if n = 0 then acc else fak (n-1, n * acc)

I denne version returnerer vi umiddelbart efter det rekursive kald og
funktionen er således halerekursiv.

Halerekursion er interresant fordi alle moderne oversætter for
funktionssprog optimerer koden (man behøver ikke opsætte stackframes
og hvad har vi). Når man programmere i sådant et sprog er det en
vigtig optimering man kan lave som programmør.

Jeg håber det gav mening.

Mvh
--Henning Niss