Rekursiver Funktionsaufruf (AVR)

> kann es da Probleme mit dem Rekursiven Funktionsaaufruf geben?

Probleme kann es immer geben :-)
Kann, muss aber nicht.

> Kann ich das im Vorfeld schon mit einem Tool checken, wieviel
> Speicher im worstcase mit der Rekursion draufgeht?

Den tatsächlichen Speicherverbrauch kann man nur
feststellen indem das Programm läuft. Allerdings könnte
man das in einem Simulator machen.

> Oder was gibt es da für möglichkeiten?
Eine Möglichkeit ist zb. folgende:

Du sorgst dafür, dass am Anfang der Speicher in dem der
Stack residiert mit einem Bitmuster gefüllt wird, zb 0xAA
dann lässt du das Programm laufen und wenn es durchgelaufen
ist, schaust du dir den Speicher wieder an. Alles was immer
noch 0xAA ist, ist offensichtlich niemals angetascht worden.
Zur Sicherheit macht man das dann noch mit einem 2-ten
Muster (was ist, wenn zufällig 0xAA auf den Stack geschrieben
wurde), zb. 0x55.
Damit kannst du feststellen, wieviel Stack in diesem einen
Programmlauf verbraucht wurde. Es liegt dann an dir dein
Programm so zu bedienen, dass du den Fall 'maximaler
Stackverbrauch' vorliegen hast.

Anmerken sollte man noch: Nur mir den Mitteln einer Hochsprache ist
das etwas schwierg zu lösen. Du wirst also darauf angewiesen sein,
dass die dein Simulator funktionen bereitstellt, mit denen
du vor und nach Programmausführung an den simulierten Speicher
rankommst.

Rekursionen sind eine spezielle mathematische Schreibweise und daher
nicht so effizient, wie andere Lösungen.

Sie sind teilweise sogar extrem ineffizient, wenn darin mehrere
Vorgänger benötigt werden, da dann Rekursionen exponentiell umsonst
berechnet werden müssen.


In der Regel lassen sich Rekursionen einfach in Schleifen umformen und
laufen dann viel schneller und benötigen viel weniger Speicherplatz.


Peter

Also wenn wir hier von KI sprechen, dann sind diese rekursiven Sachen
wohl höchstwahrscheinlich Suchoperationen in einem potentiell sehr
grossen Zustandsraum - vermutlich eine Art MIN-MAX-Algorithmus. Solche
Sachen lassen sich nun wieder in der Regel NICHT in Schleifen umformen
(wenn wir mal von speziellen Zustandsräumen absehen). Das einzige was
da bleibt ist es "nutzlose" Zweige möglichst früh zu erkennen und
nicht abzuarbeiten.

Alternative zur oben geschriebenen Analyse wäre, sich den erzeugten
Assemblercode anzusehen und mal zu zählen wie viele push/pop und
call/ret (2Byte) bei jeder Rekursion insgesammt ausgeführt werden. Dann
diese Zahl mit der Suchtiefe multiplizieren. Bei meiner 4-Gewinnt
Routine schafft ein AVR rund 6 Rekursionen bei weniger als 1KB RAM
Verbrauch. Für mehr ist der AVR schlicht zu langsam, der Speicher ist
aber (zumindest bei mir) kein Problem.