sslug-teknik team mailing list archive

["Keld Laursen" <kl@xxxxxxxxxx>]

Henning Niss <hniss@xxxxxxx> skrev i en
nyhedsmeddelelse:yc8ln51ml1p.fsf@xxxxxxxxxxx...
"Keld Laursen" <kl@xxxxxxxxxx> writes:
[snip]
Rekursiv:
  fun fak n = if n = 0 then 1 else n * fak(n-1)
[snip]
Halerekursiv:
  fun accfak (n, acc) = if n = 0 then acc else fak (n-1, n * acc)
[snip]

Så forskellen skulle være at den første version er nødt til at kalde hele
vejen til bunden af rekursiviteten(?), hvorimod den anden version kan
"returnere" til sig selv med nye parametre, så for stor stakbrug kan
undgåes? Den endelige, terminerende, rutine må så finde ud at returnere til
det kaldende sted.

Det kræver vist lidt gennemgang af assemblerkode at finde ud af om min Gnu C
kan gøre det på nogle targetmaskiner, hvor jeg ikke har for meget
hukommelse. Normal kig på rutinen ville egentlig (for mig) betyde mere brug
af stak, idet jeg nu overfører endnu en variabel.

De fleste oversættere jeg har ville opfatte den halerekursive funktion a la:

fak (n, acc)
if n <> 0
    mul acc, n
    dec n
    call fak
return acc

Håndoptimeret ville det selvfølgelig blive noget a la:

fak (n, acc)
    mul acc, n
    dec n
    jnz n, fak
return

Det må godt nok være svært at skrive gode optimeringer til compilere, til
forskel fra at skrive en "dum" compiler!

Tak for info.

Keld Laursen