Newsgroup: it.comp.lang.pascal
Titolo: Ricorsione

Ciao a tutti, qualcuno saprebbe dirmi dove trovare una guida decente sulle
procedure ricorsive? Ho un esame tra quache giorno e gli appunti del prof
sono scritti in aramaico antico...
Tnx
HellSpawn

Ad esempio voi questo come lo fareste?
Assegnata un stringa di lunghezza pari determinare se essa è palindroma sia
utilizzando un algoritmo ricorsivo che mediante uno stack.
Es. abgfrttrfgba => palindroma abfgrttrfgba => non palindroma
Datemi na mano plz:)
HellSpawn

 mediante uno stack.
? che intrendi?
Il Razziatore,
The Only Good Windows is an uninstalled Windows
-----------------------------------------------
E-MAILs : IlRazziat...@NOSPAMnetscape.net
ICQ     : 67552596
-----------------------------------------------
Founder of MediaPlayer Project
http://mpp.iwebland.com

> Ad esempio voi questo come lo fareste?
beh se potessi, non lo farei con la ricorsione, ne' con lo stack :-)
ma ovviamente devi seguire il testo... di solito quando si scrive
una procedura ricorsiva, un po' come quando si dimostra qlcs
per induzione, si ha bisogno di due cose:
a) una _base_ da cui partire, qualcosa che non richieda ulteriori
calcoli ma dia immediatamente un risultato.  Di solito la base
quando lavori con le stringhe e' la stringa vuota, o la piu' piccola
stringa che puo' capitare
b) un _passo_ di riduzione del problema, ovvero un modo per
ridurre il problema ad uno piu' piccolo e per dare un risultato
in base al risultato di esso.   Per le stringhe di solito il problema
si semplifica lavorando su una sottostringa propria della stringa
Nel caso particolare direi:
(a) la stringa vuota e' palindroma (*)
(b) una stringa e' palindroma se i due estremi sono uguali e
    la parte centrale e' palindroma.
es:    abcddcba > bcddcb > cddc > dd > [ ]
che in pseudocodice si traduce in (credo)
function palindroma(s: string): boolean;
 if s = "" then
   return true
 else if  s[1] = s[length(s)] then
   return palindroma(copy(s, 2, length(s)-2) );
end
Con lo stack cambia il modo di analizzare la stringa: puoi mettere
da parte i caratteri uno per volta fino a meta' stringa, poi iniziare
a tirarli fuori confrontandoli con il resto della stringa. Qualcosa
del genere:
palindroma := true;
for n := 1 to length(s) /2 do
 push(s[n]);
for n := 1+length(s)/2 to length(s) do
 if pop( ) <> s[n] then
  palindroma := false;
  { + break  se vuoi ottimizzare }
(*) non so' se e' vero, ma per l'algoritmo lo supponiamo
-- 
Dreadnaut
(Life would be easier if I had the source code)
 
http://dreadnaut.servebeer.com/

> Function Palindroma ( St : String ) : Boolean;
Razz... devo postare tutti gli errori che hai fatto in questa
funzione o li trovi da solo ? :-)


 Dreadnaut
Ho fatto proprio nella maniera in cui hai detto tu e devo dire che mi è
sembrata la soluzione migliore, cmq sono d'accordo nel non farla nè
ricorsivamente nè tramite stack ^_^
Ora ho questo che mi sta fregando:
Assegnata una lista di interi, scrivere una funzione ricorsiva che conti
quanti numeri primi sono presenti nella lista.
Grazie ancora per gli aiuti ! :)
HellSpawn

 quanti numeri primi sono presenti nella lista.
pensa ad una base e pensa ad un passo...
- nella lista vuota non ci sono primi,
- in una lista se la testa e' un primo ci sono
   1 + (numero_di_primi_nel_resto_della_lista) altrim solo
        (numero_di_primi_nel_resto_della_lista)
la funzione primo( ) beh e' sempre la solita, se cerchi indietro ne troverai
mille... vai da 1 a sqrt(n) e provi a dividere, se ci riesci non e' primo.
-- 
Dreadnaut
(signless perche' in trasferta)


Ho provato così e la ricorsione sembra funzionare, buffamente è la funzione
primo( ) che restituisce true a valori come 14 e 18...credo sia un problema
di arrotondamento, per eseguire il ciclo ho provato sia con trunc che con
round ma il risultato è stato identico!
Grazie 1000 cmq, mi hai chiarito un po' il panorama sulla ricorsione ;)))
HellSpawn

funzione o li trovi da solo ? :-)
Muble? appare un == non trovo nulla


Dunque ora il problema è il seguente:
Assegnato un albero BST di numeri interi, fornire una funzione ricorsiva che
dica quanti nodi, la cui chiave è un numero dispari, hanno sottoalbero
destro nullo.
Per farlo ho pensato di implementare la seguente funzione:
Function NumVuoti(alb:puntatore):integer;
var
primo,punta:puntatore;
begin
primo:=alb;
if (primo^.sx=NIL)AND(primo^.dx=NIL) then NumVuoti:=0
 else
  begin
   if alb^.sx^.num mod 2 <> 0 then
      if alb^.sx^.dx=NIL then NumVuoti:=1+NumVuoti(alb)
        else
   if alb^.dx^.num mod 2 <> 0 then
       if alb^.dx^.dx=NIL then NumVuoti:=1+NumVuoti(alb)
         else
   NumVuoti:=NumVuoti(alb);
  end;
end;
Arrivato qui non riesco a trovare il modo per semplificare il problema, ho
provato sulla falsa riga di quanto detto sulle liste coi numeri primi ma non
sono riuscito a trovare una maniera analoga con gli alberi (Dreadnaut ormai
sei il mio guru ^_^)
Tnx
HellSpawn

 sia con trunc che con round ma il risultato è stato identico!
boh, prova a usare il mod invece che dividere. Un numero primo da'
mod diverso da zero per ogni numero diverso da 0 e 1, se da' zero
vuol dire che e' multiplo, quindi non primo.


 problema
sempre cercare di richiamare la funz. ricorsiva su un "sottoinsieme"
del problema come la stringa centrale oppure i due sottoalberi.
Le proc. ric. sugli alberi di solito hanno come base le foglie e come
passo qualcosa che valutata la funzione sui *figli* (non su se' stessi)
e restituisce un risultato.


> Muble? appare un == non trovo nulla
ehhehe a quanto pare mi tocca :-)
    Then Palindroma := True;
il ";" alla fine, c'e' un else dopo
    Else If Length ( St ) Div 2 = 0
qual'e' quel numero che diviso per due da' zero? zero stesso!
forse intendevi mod, ma in fondo perche' mettercelo ?
  Then Palindroma := ( St[1] == St[Length(St) )
l'uguale-uguale l'hai visto, ma la quadra... :-)
   AND Palindroma ( Copy ( St, 2, Length ( St ) - 1) );
se parti dal 2° carattere e ne prendi length - 1 non togli
l'ultimo in fondo...  poi l'immancabile ";"
Niente di grave e non correggibile, ma da te non me
l'aspettavo :-þ hehehehheheheh


l'aspettavo :-þ hehehehheheheh
Uhm... vado a fare penitenza...


 end;
è molto contorto, sicuramente inefficiente e mi sa che non vada proprio, in
ogni caso tieni presenti le seg. cose:
 - giammai dare scontate le sezioni dichiarative, soprattutto se devi
sostenere un esame, d'accordo che è ovvio com'è fatto un albero binario ma
in un esame anche ciò che è ovvio non lo è.
 - deve andare sempre bene!!!! (cito la mia ex insegnante di info, mio
grande idolo di insegnante) ovvero tu dai scontato che il parametro non
valga mai NIL e facendo così, se passi un albero vuoto nel primo costrutto
if fai riferimento a un valore inesistene ovvero primo^.sx
al di la della ricorsione sono errori di programmazione gravi! Poi dopo ci
si lamenta che i sistemi vanno in crash :)))
Cominciamo con la sezione dichiarativa:
 Type
         alberobinario = ^albero;
         albero = Record
                          valore : integer;
                          dx,sx : alberobinario
                       end;
e infine la funzione coerentemente con la struttura che abbiamo creato:
Function howmanyoddknots(a:alberobinario):word;
Var
      app:word; {anche se in Pascal assegnare il valore alla funzione non
causa l'uscita, l'algoritmo equivalente non è portabile pertanto usiamo un
appoggio}
Begin
   app:=0; {assumiamo di non avere nodi rispondenti alle nostre
caratteristiche}
   If a<>nil then {se l'albero è vuoto si passa in fondo dove viene pertanto
restituito 0 al chiamante}
   Begin
      If ((a^.valore mod 2)<>0) and (a^.dx=nil) then inc(app); {se il
presente nodo risponde alle caratteristiche si incrementa di una unità}
      app:=app+howmanyoddknots(a^.sx)+howmanyoddknots(a^.dx) {aggiungiamo
inoltre il numero di nodi dei due sottoalberi}
   end;
   howmanyoddknots:=app; {restituiamo il nostro computo al chiamante}
end;
in questo modo creiamo una ricorsione in testa laddove ogni singola istanza
è completamente autonoma e in grado di fermare la propria esecuzione davanti
al sottoalbero vuoto.
Volendo creare la ricorsione in coda è sufficiente invertire le due righe
dentro alla sequenza del then.
Da notare che anche il tipo di dato della funzione è stato opportunamente
commisurato allo scopo, come anche la variabile d'appoggio coerente con la
funzione.
sperando di essere arrivato in tempo per il tuo esame
salutiZ
Fabio

 
Function ispalindrome(s:string):boolean;
Var
     app:boolean;
     l:byte;
Begin
   app:=False;  {partiamo dal falso}
   l:=length(s);{calcoliamo la lunghezza 1 volta x tutte}
   If l<>0 then {se la stringa non č vuota}
   Begin
     {intanto guardiamo se sono uguali la prima e l'ultima lettera}
     app:=(s[1]=s[l]); {se uguali app diventa True}
     {poi passiamo l'esame alla sottostringa piů centrale}
     If l>2 then app:=app and ispalindrome(copy(s, 2, l-1))
   end;
   ispalindrome:=app  {restituiamo il computo al chiamante}
end;


Ormai il dado è tratto, speriamo bene... :)
Grazie x il tuo aiuto cmq!
HellSpawn