Tak på rekursive kall i C++ ?

[gizmo45]

Jeg sliter med et snodig problem i et C++ program:

 

I korte trekk tar det inn et binært svart/hvitt BMP bilde og skal returnere en polygon-beskrivelse av de svarte objektene i bildet. Problemet er at hvis de sorte objektene blir for store så avslutter bare programmet midt i uten noen feilmelding eller noe.

 

Hvis jeg deler opp objektene i mindre deler i f. eks. paint først (tegne noen hvite streker for å splitte de største sammenhengende strukturene så funker det fint.

 

 

Jeg har funnet ut at programmet exit'er i funksjonen under. Dette er en rekursiv funksjon som velger ut nærliggende bildepunkter som er innenfor samme objekt.

 

Altså, jo større objekt jo flere rekursive kall vil man få.

 

Vel, det jeg lurer på er om det finnes noe tak for maks rekursive kall i C/C++ eller noe slikt, som gjør at programmet umiddelbart avslutter hvis dette skjer. Synes det er noe rart ettersom ingen feilmelding vises, men har ingen annen anelse om hva som kan være grunnen. Hvis noen har noen anelse om hva som kan forårsake dette er jeg ytterst takknemlig!

 

(funksjonen er forenklet noe)

 

void fillNeighbourhood(int posX, int posY, int *img, int imgW) { 

 if (img[posX+posY*imgW] == black_color){

   img[posX+posY*imgW]=0;

   fillNeighbourhood(posX+1,posY  , img, imgW);
   fillNeighbourhood(posX+1,posY+1, img, imgW);
   fillNeighbourhood(posX+1,posY-1, img, imgW);
   fillNeighbourhood(posX-1,posY  , img, imgW);
   fillNeighbourhood(posX-1,posY+1, img, imgW);
   fillNeighbourhood(posX-1,posY-1, img, imgW);
   fillNeighbourhood(posX,posY+1, img, imgW);
   fillNeighbourhood(posX,posY-1, img, imgW);

 }
}

Endret 27. april 2007 av gizmo45

[Giddion]

ja det finnes et tak, men jeg er ikke sikker på om det ligger i c++ eller i cpuen.

 

jeg laga et program (under) som lager en stack overflow som indikerer at det er for mange rekursiv funksjoner. Når feilen kommer har jeg i= 4886. Det rare er at jeg ser bare feilen når debuggeren sier fra, men hvis jeg kjører uten så får jeg ingen feil og programmet bare avslutter

 

Klikk for å se/fjerne innholdet nedenfor

#include <stdio.h>

int i;
void infrec();

int main()
{
i=0;
infrec();
return 0;
}

void infrec()
{
i++;
infrec();
}

 

det finnes måter å fikse dette på (har jeg lest)

Hvilke OS bruker du?

Hvilke kompilator bruker du?

[gizmo45]

ja det finnes et tak, men jeg er ikke sikker på om det ligger i c++ eller i cpuen.

 

jeg laga et program (under) som lager en stack overflow som indikerer at det er for mange rekursiv funksjoner. Når feilen kommer har jeg i= 4886. Det rare er at jeg ser bare feilen når debuggeren sier fra, men hvis jeg kjører uten så får jeg ingen feil og programmet bare avslutter

 

Klikk for å se/fjerne innholdet nedenfor

#include <stdio.h>

int i;
void infrec();

int main()
{
i=0;
infrec();
return 0;
}

void infrec()
{
i++;
infrec();
}

 

det finnes måter å fikse dette på (har jeg lest)

Hvilke OS bruker du?

Hvilke kompilator bruker du?

8483555[/snapback]

 

 

Hei,

 

Takk for svar.

 

Ah, det kan forklare saken! Jeg forsøkte nettopp å kjøre med debug og da får jeg en stack-error, men som deg, ingen indikasjon på feil ved å kjøre uten debug. Hmm, snodig...

 

Jeg bruker MS Visual Studio 2005 på en WinXP maskin.

 

PS:

Forsøkte programmet ditt og fikk stack overflow exception på i=4868. Sikker på det var 4886 og ikke 4868 du fikk?

Endret 27. april 2007 av gizmo45

[Dead_Rabbit]

Dette er hvor langt jeg kom.

#include <iostream>

using namespace std;

void recursive(int i)
{
       cout << i << endl << flush;
       recursive(++i);
}

int main(int argc, char* argv[])
{
       recursive(0);
       return 0;
}

$ g++ rec.cpp -o rec
$ ./rec
1
2
[...]
524023
Segmentation fault (core dumped)

Tallet jeg får varierer noe også..

[4WheelDrive]

Hei sveis!

 

Ved mange rekursive kall vil stacken til slutt fylles. Ved hvert nye rekursive funksjonskall blir den forrige funksjonens variabler, return-pointer o.l. liggende på stacken (helt til du returnerer).

 

For å utsette problemet kan man øke stack-sizen. I Visual Studio tror jeg det gjøres under prosjekt settings -> Linker -> Stack el.l.

 

Når dere kjører programmet i debug, kobles ofte debuggeren automatisk til den kjørende prosessen, slik at debuggeren tar kontroll når feilen inntreffer. I release mode må man ofte selv koble debuggeren mot prosessen. Har man ikke gjort det vil programmet bare avsluttes (eventuelt Just-In-Time Debugges om man har konfigurer dette).

[krislarsen]

Hei sveis!

 

Ved mange rekursive kall vil stacken til slutt fylles. Ved hvert nye rekursive funksjonskall blir den forrige funksjonens variabler, return-pointer o.l. liggende på stacken (helt til du returnerer).

 

For å utsette problemet kan man øke stack-sizen. I Visual Studio tror jeg det gjøres under prosjekt settings -> Linker -> Stack el.l.

 

Når dere kjører programmet i debug, kobles ofte debuggeren automatisk til den kjørende prosessen, slik at debuggeren tar kontroll når feilen inntreffer. I release mode må man ofte selv koble debuggeren mot prosessen. Har man ikke gjort det vil programmet bare avsluttes (eventuelt Just-In-Time Debugges om man har konfigurer dette).

8485592[/snapback]

Dette stemmer ja.. På mikrokontrollere må man være spesielt nøye med å ikke bruke mange rekursive kall, pga. stacken flyter over meget fort. Men på en vanlig PC er det vel ikke mange situasjoner dette blir et problem vil jeg tro.. Hvor store bilder er det snakk om her? Ser du iallfall sender inn peker og ikke allokerer minne for hvert rekursive kall

[Zolo]

Har du prøvd å gå ned til 4 naboers floodfill istedet for 8?

[krislarsen]

Kan vel legge til at et triks er å ikke bruke automatiske variable inni funksjonen du kaller rekursivt, men heller globale variable i den grad det lar seg gjøre.

 

F.eks. kan du la int *img og int imgW være globale, slik at du slipper å ta dem inn i hvert eneste kall. Altså så lenge disse er like for alle kallene du foretar. Regner med det kan hjelpe på litt..

[gizmo45]

Hei sveis!

 

Ved mange rekursive kall vil stacken til slutt fylles. Ved hvert nye rekursive funksjonskall blir den forrige funksjonens variabler, return-pointer o.l. liggende på stacken (helt til du returnerer).

 

For å utsette problemet kan man øke stack-sizen. I Visual Studio tror jeg det gjøres under prosjekt settings -> Linker -> Stack el.l.

 

Når dere kjører programmet i debug, kobles ofte debuggeren automatisk til den kjørende prosessen, slik at debuggeren tar kontroll når feilen inntreffer. I release mode må man ofte selv koble debuggeren mot prosessen. Har man ikke gjort det vil programmet bare avsluttes (eventuelt Just-In-Time Debugges om man har konfigurer dette).

8485592[/snapback]

 

Tusen takk for dette tipset! Under Project Properties -> Linker -> System satte jeg parameteren Stack Reserve Size til 10000000 (10 MB), og det fungerer utmerket!

 

Evig takknemlig!

[Dead_Rabbit]

Evt. så kan vel sikkert pekere brukes hvis du vil spare litt på stakken. (Altså, istedenfor å bruke globale variabler, som jo er litt fy-fy..