Sollen wir rekursive Aufrufliste als Hilfsraum betrachten?

Question

Sollten wir rekursive Aufrufliste als Hilfsraum von dem Programm verwendet betrachten? Ich denke, es sollte nur bei der Berechnung der Raumkomplexität berücksichtigt werden, nicht aber bei der Berechnung des Hilfsraums.

---

Hilfsabstand ist der zusätzliche Platz oder der temporäre Platz, der von einem Algorithmus verwendet wird. Raumkomplexität eines Algorithmus ist der Gesamtraum, den der Algorithmus in Bezug auf die Eingabegröße einnimmt.

Answer 1

Wenn Sie sich tatsächlich auf Variablen in äußeren Aufrufen verlassen — Wenn Sie sie wieder benötigen, nachdem Ihr innerster Aufruf — zurückgibt, dann ja, sollten sie in den Hilfsraum aufgenommen werden.

Aber wenn alles, was Sie haben, sind tail calls, und der einzige Grund, warum Ihr Stapel wächst, ist, dass Ihr Compiler keine Tail-Call-Optimierung unterstützt, dann glaube ich nicht, dass ich das in den Hilfsraum der berücksichtigen würde) Algorithmus, obwohl Ihre tatsächliche Implementierung am Ende diesen Raum einnehmen wird.