Rekursivitet i PHP

Fråga

Jag håller på med ett rekursivt script. Jag har testat det och det fungerar bra upp till en viss nivå, men när det blir fråga om lite mer komplicerad input stannar det utan felmeddelande. Precis som om minnet tar slut eller nåt sådant. I Apache-loggen står det: child pid 7638 exit signal Segmentation fault (11)

Jag har gjort det som ett CLI och då får jag ”Segmenteringsfel”.

Koden är rätt, men förmodligen gör jag något logiskt fel. Har försökt googla, men segmenteringsfel verkar kunna vara i stort sett vilket programmeringsfel som helst som orsakas av att man försöker komma åt minnet på ett felaktigt sätt.

Jag har ändrat error reporting mm:

ini_set(”error_reporting”, ”E_ALL”); ini_set(”display_errors”, ”On”); ini_set(”memory_limit”, -1); ini_set(”max_execution_time”, 0);

men det verkar som om det inte spelar någon roll. Får inget meddelande om vad som är fel.

Det finns ett Return, men det kan ta ca 5-6 tusen rekursiva anrop innan detta inträffar. Själva funktionen är liten och tar inte mycket minne. Ska inte detta gå?

/Hälsningar jodomama

Svar

Hej Jodomama.

När man använder rekursivitet så kommer varje anrop att använda en del av stacken, bland annat för parameteröverföring men även för lokala variabler och återhoppsadress.

Ett sätt att minska mängden allokerad data på stacken är att använda heapen istället. Dock kommer eventuella pekare ta plats i stacken.

Vid några tester i PHP5.2.8 kom vi fram till följande minnesgränser,

memory_limit: 1M
rekursioner 5421
fel: Fatal error: Allowed memory size of 1048576 bytes exhausted (tried to allocate 40 bytes) in

memory_limit: 2M
rekursioner 11126
fel: Fatal error: Allowed memory size of 2097152 bytes exhausted (tried to allocate 40 bytes) in

memory_limit: 4M
rekursioner 19184
fel (i syslog): child pid 2066 exit signal Segmentation fault (11)

memory_limit: 128M
rekursioner 19184
fel (i syslog): child pid 2066 exit signal Segmentation fault (11)

memory_limit: 256M
rekursioner 19184
fel (i syslog): child pid 2066 exit signal Segmentation fault (11)

Som du ser har vi provat att utöka minnet, vilket hjälper till en viss mån. Men tillsist uppkommer ändå en gräns som begränsar antalet anrop (19184 st anrop)

På http://bugs.php.net/bug.php?id=43187 kan man läsa mer om PHPs ståndpunkt i denna fråga.

Är det tail recusion (se http://en.wikipedia.org/wiki/Tail_recursion) kan man lätt skriva om metoden. Självklart kan du även skriva om andra typer av rekursioner, men det kan vara besvärligare.

Oavsett ser det tyvärr ut som du får skriva om din källkod.

Lycka till