Recursions

Memoràndum al respecte de típiques funcions recursives que he programat per a diversos usos en Pascal. S’inclouen funcions com de test de nombres (primers/compostos), factorial, obtenció de paraula n-èssima d’una frase, etc.

Les següents porcions recursives de codi formen part de la unitat vapbasics.tpu, algunes posteriors consideracions poden passar per l’actualizació d’alguns tipus de variables per altres més potents o actuals.

FUNCIÓ FACTORIAL:

Function Factorial(i:Longint):Longint;
 Begin
   If i<2 Then factorial:=1 Else factorial:=factorial(i-1)*i;
 End;

FUNCIÓ ISPRIME (v0.1):

Function isprime (i:Longint):Boolean;
   Function isprimeaux(i:Longint;n:Longint):Boolean;
         Begin
         If (i<3) Then isprimeaux:=True Else
                 If (n Mod (i-1))=0 Then isprimeaux:=False Else
                    isprimeaux:=isprimeaux (i-1,n);
         End;
   Begin
    isprime:=isprimeaux((i div 2)+1,i);
  End;

Anàlisi de millores(v0.6).

Atès que la probabilitat que donat un nombre qualsevol aquest siga parell o senar és simètricament d’1/2, resulta també evident que el fet que siga múltiple de tres és d’un terç. D’esta forma resulta evident per inducció què, a mesura que augmenta el nombre candidat a ser divisor també minva la probabilitat que realment ho siga, la qual cosa ens porta a redefinir les funcions atès a que tal i com com està definit fins ara hi ha un augment substancial del cost computacional de l’algorisme proposat front a si treballarem de baix cap amunt enlloc des de la meitat cap avall. Açò es pot implementar per exemple, o bé en una simple diferència de complement en la segona condicional a l’estil del mòdul respecte a (n div 2+1)-i+1 de manera que s’inverteix el sentit del nombre candidat a divisor, o bé simplement revertint l’ordre d’anàlisi de candidats i incloent el càlcul límit (i div 2) en isprimeaux (o com un tercer paràmetre). D’esta darrera forma el codi queda així:

Function isprime (i:Longint):Boolean;
 Function isprimeaux(i:Longint;n:Longint;mid:Longint):Boolean;
 Begin
   If (i>mid) Then isprimeaux:=True Else
     If (n Mod i)=0 Then isprimeaux:=False Else 
       isprimeaux:=isprimeaux (i+1,n,mid);
    End;
Begin
  isprime:=isprimeaux(2,i, i Div 2);
End;

Com hem dit, cal fixar-se en que s’ha inclòs un tercer paràmetre en la funció auxiliar per tal d’evitar el calcul de la meitat del nombre en cadascuna de les autocridades de la funció, evitant així cost computacional innecessari.

FUNCIONS D’OBTINDRE ELEMENTS D’UNA CADENA:

Function GetWord (var s:String;n:Integer):String; {nth word}
 Var Aux:String;l:Integer;
  Begin
    l:=Pos(' ',s); Aux:=Copy(s,l+1,Length(s)-l+1);
    If n>1 Then GetWord:=GetWord(aux,n-1) Else
         GetWord:=Copy(s,1,Pos(' ',s)-1);
  End;
 
Function cdr(s:String):String; {Content of decrement register}
   Begin cdr:=Copy(s,Pos(' ',s)+1,Length(s)-Pos(' ',s)-1); End;
 
 Function car(s:String):String; {Content of address register}
   Begin car:=GetWord(s,1); End;