[PASCAL] Stack Overflow Error e Ricorsione

di il
5 risposte

[PASCAL] Stack Overflow Error e Ricorsione

Ragazzi ho un problema, ho scritto un algoritmo ricorsivo per il calcolo della COMPONENTE CONNESSA di una immagine.

I Pixel di questa immagine sono memorizzati in un Array bidimensionale, quindi la Componente Connessa viene calcolata a partire da un pixel dell'immagine (k quindi sarebbe un elemento dell'array).

Questo è l'algoritmo:
<pre id=code><font face=courier size= id=code>
{Procedure per il Calcolo della Componente Connessa}
procedure CalcolaCC(Riga,Colonna,PixelIniziale,s,ToniMax:integer; VAR i,j:integer);
var new_i, new_j:integer;

begin


{Verifica se gli indici individuano ancora una locazione della matrice}
If ((i<=Riga) And (j<=Colonna)) And ((i>0) And (j>0)) Then
begin
{Verifica se il pixel appartiene alla componente connessa}
If (Dati[i, j] - PixelIniziale) < s Then
begin
{Modifica della matrice che individuer… la componente connessa}
DatiAppoggio[i,j]:=1;

{Modifica del valore della matrice per far modo che la ricorsione non sia infinita}
Dati[i,j]:=2*ToniMax;

{Autoattivazione ("destra","sotto", "sinistra", "sopra")}
new_j:=j+1;
CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
new_i:=i+1;
CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
new_j:=j-1;
CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, i, new_j);
new_i:=i-1;
CalcolaCC(Riga, Colonna, PixelIniziale, s, ToniMax, new_i, j);
End;
End;

end;
</font id=code></pre id=code>

Come posso risolvere i problemi di stack overflow?

5 Risposte

  • Re: [PASCAL] Stack Overflow Error e Ricorsione

    Se stai usando il vecchio TurboPascal per DOS l'unica è cercare di aumentare lo spazio per lo stack.

    Se è un compilatore 32bit per win o linx, allora la cosa si fa triste perché così come è l'algoritmo è invariante e dal momento che sfonda lo stack significa solo due cose o effettua troppe chiamate o alloca troppa memoria per ogni chiamata; quindi è del tutto inutile usarlo con la ricorsione, meglio renderlo iterativo in modo da poter gestire "in prorprio" almeno lo stack e fermarsi prima che lo schianti in automatico con i push dal SO.

    Chip
  • Re: [PASCAL] Stack Overflow Error e Ricorsione

    In che modo lo renderesti iterativo...

    mi aiuti?
  • Re: [PASCAL] Stack Overflow Error e Ricorsione

    Con l'occasione sto rileggendo l'algoritmo, cosa è quella Autoattivazione()? l'algoritmo fa la ricorsione 4 volte ogni volta o solo una delle 4 viene chiamata? cioè sono mutuamente esclusive le 4 chiamate?

    http://www.eleves.ens.fr/home/defeo/serio/english/papers/hanoi/iterative.htm
    con il metodo iterativo praticamente facciamo noi il lavoro dello stack del SO ma prima va saputo bene che fa adesso questo algoritmo

    Chip
  • Re: [PASCAL] Stack Overflow Error e Ricorsione

    L'algoritmo è un po complicato da spiegare...intendo per quello che dovrebbe fare...ci provo..

    Deve calcolare la componente connessa di una immagine che è memorizzata in una matrice. In questa matrice in pratica sono memorizzati i valori dei vari pixel dell'immagine.

    La componente connessa è un percorso tra gli intorni di un determinato pixel.


    ----------------------------
    | 0 | 5 | 0 | 0 | 0 | 5 | 0|
    ----------------------------
    | 0 | 5 | 5 | 5 | 0 | 5 | 0|
    ----------------------------
    | 5 | 0 | 0 | 5 | 0 | 5 | 5|
    ----------------------------
    | 5 | 0 | 5 | 5 | 5 | 5 | 5|
    ----------------------------

    ora prendendo in esame la matrice che ho disegnato...si sceglie un PixelIniziale, ad esempio quello in posizione (1,2).

    A partire da questo pixel si analizzano i pixel adiacenti a NORD, SUD, EST, OVEST se questi pixel rientrano in un intervallo di valori (nella funzione chiamato "S") allora costituiscono un intorno del nostro pixel.

    poi a partire da ogni intorno si procede allo stesso modo...

    per questo la procedura è richiamata 4 volte...una per ogni punto cardinale, esempio:

    0 1 0
    1 2 1
    0 1 0

    Il 2 sarebbe il nostro ipotetico pixel iniziale e quelli marchiati con 1 sarebbero gli ipotetici intorni.

    capito più o meno?
  • Re: [PASCAL] Stack Overflow Error e Ricorsione

    Non ci credo... Finalmente trovo qualcuno che compila ancora in Pascal, mio primo amore...

    Born in the wind, born to be wild!
Devi accedere o registrarti per scrivere nel forum
5 risposte